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
Communication complexity of document exchange2000
Construction of visual secret sharing schemes with almost optimal contrast2000
Dimensionality reduction techniques for proximity problems2000
Efficient bundle sorting2000
Estimating DNA sequence entropy2000
Faster deterministic dictionaries2000
Fast practical solution of sorting by reversals2000
Height in a digital search tree and the longest phrase of the Lempel-Ziv scheme2000
Improved bandwidth approximation for trees2000
Improved bounds on the sample complexity of learning2000
Improved classification via connectivity information2000
New and improved algorithms for minsum shop scheduling2000
On deciding stability of scheduling policies in queueing systems2000
On external memory graph traversal2000
On incremental rendering of silhouette maps of polyhedral scene2000
On local search and placement of meters in networks2000
On the complexity of bicoloring clique hypergraphs of graphs (extended abstract)2000
On the red-blue set cover problem2000
On the temporal HZY compression scheme2000
Optimizing the sum of linear fractional functions and applications2000
Randomized greedy hot-potato routing2000
Scheduling to minimize average stretch without migration2000
Sweeping simple polygons with a chain of guards2000
Testing and spot-checking of data streams (extended abstract)2000
Towards a 4/3 approximation for the asymmetric traveling salesman problem2000
TSP-based curve reconstruction in polynomial time2000
A Convex Relaxation for the Asymmetric TSP1999
A Deterministic Approximation Algorithm for a Minmax Integer Programming Problem1999
A Formal Treatment of Remotely Keyed Encryption1999
Approximation Algorithms for Bipartite and Non-Bipartite Matching in the Plane1999
A Practical Clustering Algorithm for Static and Dynamic Information Organization1999
A Slique Size Bounding Technique with Application to Non-Linear Codes1999
A Small Approximately min-wise Independent Family of Hash Functions1999
Beating the Logarithmic Lower Bound: Randomized Preemptive Disjoint Paths and Call Control Algorithms1999
Checking Priority Queues1999
Clustering in Large Graphs and Matrices1999
Dynamic LCA Queries on Trees1999
Estimating Interpolation Error: A Combinatorial Approach1999
Geometric Matching Under Noise: Combinatorial Bounds and Algorithms1999
Group Signatures Á la carte1999
Improved Bicriteria Existence Theorems for Scheduling1999
Just the Fax - Differentiating Voice and Fax Phone Lines Using Call Billing Data1999
Kinetic Collision Detection Between Two Simple Polygons1999
LP-based Analysis of Greedy-dual-size1999
Minimizing Weighted Completion Time on a Single Machine1999
Minimizing Wirelength in Zero and Bounded Skew Clock Trees1999
Motion Planning of a Ball Amid Segments in Three Dimensions1999
New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning1999
On-line Complexity of Monotone Set Systems1999
On Multi-Dimensional Packing Problems1999

« prev Page 38/41 next »