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
Improved lower bounds for embeddings into L12006
Knapsack auctions2006
l22 spreading metrics for vertex ordering problems2006
Leontief economies encode nonzero sum two-player games2006
Local versus global properties of metric spaces2006
Lower bounds for asymmetric communication channels and distributed source coding2006
Matrix approximation and projective clustering via volume sampling2006
Max-tolerance graphs as intersection graphs: cliques, cycles, and recognition2006
New lower bounds for oblivious routing in undirected graphs2006
Oblivious network design2006
On nash equilibria for a network creation game2006
On the competitive ratio of evaluating priced functions2006
On the tandem duplication-random loss model of genome rearrangement2006
Query-efficient algorithms for polynomial interpolation over composites2006
Random graphs2006
Randomized incremental constructions of three-dimensional convex hulls and planar voronoi diagrams, and approximate range counting2006
Sampling algorithms for l2 regression and applications2006
Scalable leader election2006
Self-improving algorithms2006
Single-minded unlimited supply pricing on sparse instances2006
Small hop-diameter sparse spanners for doubling metrics2006
Streaming and sublinear approximation of entropy and information distances2006
Testing triangle-freeness in general graphs2006
The complexity of matrix completion2006
The complexity of quantitative concurrent parity games2006
The hunting of the bump: on maximizing statistical discrepancy2006
The price of being near-sighted2006
The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema2006
Tight approximation algorithms for maximum general assignment problems2006
Weighted isotonic regression under the L1 norm2006
A group-strategyproof mechanism for Steiner forests2005
A multiple-choice secretary algorithm with applications to online auctions2005
An asymptotic approximation scheme for multigraph edge coloring2005
A new look at survey propagation and its generalizations2005
An optimal Bloom filter replacement2005
An optimal dynamic interval stabbing-max data structure?2005
An optimal online algorithm for packet scheduling with agreeable deadlines2005
Approximating the average response time in broadcast scheduling2005
Approximation algorithms for low-distortion embeddings into low-dimensional spaces2005
A tight threshold for metric Ramsey phenomena2005
Bidimensionality: new connections between FPT algorithms and PTASs2005
Coins make quantum walks faster2005
Collusion-resistant mechanisms for single-parameter agents2005
Computing equilibria in multi-player games2005
Controlled perturbation for Delaunay triangulations2005
Delaunay triangulations approximate anchor hulls2005
Deterministic network coding by matrix completion2005
Distributed approaches to triangulation and embedding2005
Efficient hashing with lookups in two memory accesses2005
Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut2005

« prev Page 33/41 next »