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.
Top Authors
Impactful Papers
Papers from this venue that shaped research clusters.
Foundational
Labelings vs. Embeddings: On Distributed Representations of Distances
foundational
Compact Distance Labeling for Metric Spa
2020
Quantum Algorithms for the Triangle Problem
foundational
Quantum Subgraph Finding and Graph Spars
2005
Approximating Hereditary Discrepancy via Small Width Ellipsoids
foundational
Spectral and Geometric Bounds for Heredi
2015
List-color-critical graphs on a fixed surface
foundational
Finiteness and Structure of Critical Gra
2009
Improved Concentration Bounds for Count-Sketch
foundational
Symmetrization and Variance Based Repres
2014
Counting without sampling: new algorithms for enumeration problems using statistical physics
foundational
Analytical and Asymptotic Counting of Gr
2006
Testing Planarity of Partially Embedded Graphs
foundational
SPQR Trees for Constrained Graph Embeddi
2010
Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions.
foundational
The Adaptivity Gap in Stochastic Optimiz
2016
Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding
foundational
Intrinsic Dimension Matrix Concentration
2011
Influential
Approximating matching size from random streams
influential
Space Complexity of Random Order Data St
2014
A Hybrid Sampling Scheme for Triangle Counting
influential
Wedge Sampling for Estimating Graph Moti
2017
Transitive-closure spanners
influential
Hardness of Approximating Graph Spanners
2009
A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
influential
Sublinear Time Algorithms for Massive Gr
2012
How to Sell Hyperedges: The Hypermatching Assignment Problem
influential
Lift and Project Hierarchies for Combina
2013
A Refined Laser Method and Faster Matrix Multiplication
influential
The Computational Intractability of Tens
2021
Sparse induced subgraphs in P6-free graphs
influential
Structural Parameterization via Treedept
2024
Learning from satisfying assignments under continuous distributions
influential
The Quasipolynomial Barrier in Learning
2020
On Simultaneous Two-player Combinatorial Auctions
influential
Transitioning from Monte Carlo to Determ
2018
Prophet Inequalities with Limited Information
influential
Learning Optimal Auctions from Finite Sa
2014
Related Venues
Venues with the most similar research cluster distributions.
SIAM Journal on Computing81% similar · 966 papers
STOC79% similar · 1,631 papers
Esa78% similar · 632 papers
ICALP77% similar · 1,234 papers
FOCS74% similar · 1,306 papers
ACM Trans. Algorithms74% similar · 355 papers
Approx-random69% similar · 404 papers
J. ACM66% similar · 532 papers
Ipco63% similar · 244 papers
Stacs61% similar · 357 papers