SODA

2,036 papers555 directions
SODA (Symposium on Discrete Algorithms) is a research venue active since 1990 that focuses on the design and analysis of discrete algorithms. With a corpus of over 2,500 papers, it serves as a foundational outlet for theoretical research that informs machine learning and artificial intelligence. The venue is characterized by its emphasis on approximation algorithms, combinatorial optimization, and the mathematical limits of computation. In the context of AI and machine learning, SODA publishes research on online matching and selection, fair division of indivisible items, and robust selection under adversarial or random arrivals. Other significant research directions include spectral methods for directed graph signal processing, fully dynamic optimization for evolving data streams, and the efficiency of auction mechanisms. The venue also features work on learning theory, such as lower bounds for decision tree learning, and the development of faster linear systems through multi-level sketched preconditioning. The venue hosts contributions from prolific researchers including Anupam Gupta, David P. Woodruff, Haim Kaplan, and Piotr Indyk. Recent publications highlight a focus on bridging asymptotic optimality with practical algorithmic efficiency, covering topics like matrix norm approximation and massively parallel minimum spanning trees. By addressing the computational costs and theoretical constraints of algorithms, SODA provides the mathematical frameworks necessary for advancing data processing and automated decision-making systems.

Papers by Year

2026 82
2025 100
2024 103
2023 97
2022 93
2021 117
2020 103
2019 116
2018 112
2017 102
2016 91
2015 79
2014 77
2013 80
2012 62
2011 57
2010 60
2009 66
2008 56
2007 51
2006 51
2005 58
2004 41
2003 38
2002 38
2001 37
2000 35
1999 40
1998 17
1997 23
1996 12
1995 15
1994 14
1993 8
1992 10
1991 14
1990 7

Top Research Directions

Research directions most represented by papers from this venue.

The Empirical Validation Gap 35
Transitioning from Monte Carlo to Deterministic Graph Algorithms 32
Tightening Theoretical Bounds by Optimizing Constant Factors 28
From Fractional Solutions to Discrete Decisions 27
The Computational Cost of High Precision 14
Extending Structural Graph Properties to Broader Graph Classes 12
Irrevocable Decisions in Online Resource Allocation 12
Incremental Maintenance of Dynamic Graph Indices 12
Closing the Optimality Gap in Online Algorithms 11
Proving Computational Intractability Through Hardness Reductions 11
Managing Hidden Constant Overhead in Algorithm Design 11
Proving Algorithmic Optimality via Complexity Conjectures 10
Online Optimization Under Adversarial Arrival Orders 10
Graph Algorithms Under Semi-Streaming Space Constraints 9
Deterministic Approximation via Spatial Correlation Decay 8

Top Authors

AuthorPapers
Anupam Gupta51
MohammadTaghi Hajiaghayi43
Chandra Chekuri35
David Woodruff33
Haim Kaplan33
Monika Henzinger26
Pinyan Lu26
Piotr Indyk24
Vahab Mirrokni24
Yossi Azar23
Aravind Srinivasan22
Benjamin Moseley21
Kurt Mehlhorn21
Robert Kleinberg21
Aaron Sidford20
Ilias Diakonikolas18
Meirav Zehavi18
Ravi Kumar18
Debmalya Panigrahi17
Shi Li17

Impactful Papers

Papers from this venue that shaped research clusters.

Foundational

Influential

Related Venues

Venues with the most similar research cluster distributions.

Papers

TitleYear
Fast convergence of selfish rerouting2005
Graph distances in the streaming model: the value of space2005
Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality2005
Isomorphism and embedding problems for infinite limits of scale-free graphs2005
Job shop scheduling with unit processing times2005
Limitations of cross-monotonic cost sharing schemes2005
Lower bound for sparse Euclidean spanners2005
LP decoding achieves capacity2005
Marriage, honesty, and stability2005
Matrix rounding with low error in small submatrices2005
Multidimensional balanced allocations2005
Near-optimal online auctions2005
New constructions of (alpha, beta)-spanners and purely additive spanners2005
Oblivious routing on node-capacitated and directed graphs2005
On hierarchical routing in doubling metrics2005
Online ascending auctions for gradually expiring items2005
Online client-server load balancing without global information2005
Online conflict-free coloring for intervals2005
Online convex optimization in the bandit setting: gradient descent without a gradient2005
On profit-maximizing envy-free pricing2005
On the approximability of some network design problems2005
On the spread of viruses on the internet2005
Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics2005
Pianos are not flat: rigid motion planning in three dimensions2005
Popular matchings2005
Primal-dual approach for directed vertex connectivity augmentation and generalizations2005
Quantum algorithms for the triangle problem2005
Rounds vs queries trade-off in noisy computation2005
Selfish routing with atomic players2005
Sharing the cost more efficiently: improved approximation for multicommodity rent-or-buy2005
Substring compression problems2005
The complexity of low-distortion embeddings between point sets2005
The expected value of random minimal length spanning tree of a complete graph2005
The hidden subgroup problem and permutation group theory2005
The influence of search engines on preferential attachment2005
Theory of semidefinite programming for sensor network localization2005
The relative worst order ratio applied to paging2005
Towards a complete characterization of tries2005
A characterization of easily testable induced subgraphs2004
A general approach to online network optimization problems2004
An improved data stream algorithm for frequency moments2004
Approximate budget balanced mechanisms with low communication costs for the multicast cost-sharing problem2004
Approximate classification via earthmover metrics2004
Approximate Nearest Neighbor under edit distance via product metrics2004
Approximation schemes for multidimensional packing2004
A stronger bound on Braess's Paradox2004
A time efficient Delaunay refinement algorithm2004
Complexities for generalized models of self-assembly2004
Computing equilibria for congestion games with (im)perfect information2004
Computing maximally separated sets in the plane and independent sets in the intersection graph of unit disks2004

« prev Page 34/41 next »