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
Online Submodular Welfare Maximization: Greedy is Optimal2013
On the Complexity of Information Spreading in Dynamic Networks2013
Optimal and Efficient Parametric Auctions2013
Output-sensitive Skyline Algorithms in External Memory2013
Packing directed cycles through a specified vertex set2013
Playing Mastermind with Many Colors2013
Poly-logarithmic Approximation for Maximum Node Disjoint Paths with Constant Congestion2013
Randomized Primal-Dual analysis of RANKING for Online BiPartite Matching2013
Reducing Revenue to Welfare Maximization: Approximation Algorithms and other Generalizations2013
Regret Minimization for Reserve Prices in Second-Price Auctions2013
Reporting neighbors in high-dimensional Euclidean spaces2013
Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes2013
Shift Finding in Sub-Linear Time2013
Simple and Nearly Optimal Multi-Item Auctions2013
Smoothed Analysis of the Successive Shortest Path Algorithm2013
Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance2013
Testing k-Modal Distributions: Optimal Algorithms via Reductions2013
Testing Low Complexity Affine-Invariant Properties2013
The Fast Cauchy Transform and Faster Robust Linear Regression2013
The Power of Linear Reconstruction Attacks2013
The Power of Non-Uniform Wireless Power2013
The Space Complexity of 2-Dimensional Approximate Range Counting2013
Totally odd subdivisions and parity subdivisions: Structures and Coloring2013
Towards (1+ε)-Approximate Flow Sparsifiers2013
Towards More Realistic Probabilistic Models for Data Structures: The External Path Length in Tries under the Markov Model2013
Towards Polynomial Simplex-Like Algorithms for Market Equlibria2013
Turning big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering2013
Turning big data into tiny data: Constant-size coresets for-means, PCA and projective clustering2013
Weighted Graph Laplace Operator under Topological Noise2013
Windows into Relational Events: Data Structures for Contiguous Subsequences of Edges2013
Є-Samples for Kernels2013
Algorithms for the transportation problem in geometric settings2012
A little advice can be very helpful2012
A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size2012
A new approach to the orientation of random hypergraphs2012
An O(log k)-competitive algorithm for generalized caching2012
An O(n2) time algorithm for alternating Büchi games2012
A polynomial-time approximation scheme for planar multiway cut2012
Approximate counting via correlation decay in spin systems2012
Approximating fixation probabilities in the generalized Moran process2012
Approximation algorithms and hardness of the k-route cut problem2012
Approximation algorithms for stochastic orienteering2012
Beyond myopic best response (in Cournot competition)2012
Black-box reductions for cost-sharing mechanism design2012
Bypassing UGC from some optimal geometric inapproximability results2012
Concentration and moment inequalities for polynomials of independent random variables2012
Concentration inequalities for nonlinear matroid intersection2012
Constant factor approximation algorithm for the knapsack median problem2012
Data reduction for weighted and outlier-resistant clustering2012
Deterministic construction of an approximate M-ellipsoid and its applications to derandomizing lattice algorithms2012

« prev Page 25/41 next »