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
Approximating LCS in Linear Time: Beating the √n Barrier2019
A PTAS for Euclidean TSP with Hyperplane Neighborhoods2019
A PTAS for ℓp-Low Rank Approximation2019
A sort of an adversary2019
Assignment Mechanisms under Distributional Constraints2019
Beating Greedy for Stochastic Bipartite Matching2019
Binary Robust Positioning Patterns with Low Redundancy and Efficient Locating Algorithms2019
Cheeger Inequalities for Submodular Transformations2019
Communication Complexity of Discrete Fair Division2019
Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation2019
Computing all Wardrop Equilibria parametrized by the Flow Demand2019
Contraction Decomposition in Unit Disk Graphs and Algorithmic Applications in Parameterized Complexity2019
Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs2019
Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs.2019
Correlation-Robust Analysis of Single Item Auction2019
Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid2019
Deterministically Maintaining a (2 + ∊)-Approximate Minimum Vertex Cover in O(1/∊2) Amortized Update Time2019
Dimension-independent Sparse Fourier Transform2019
Dynamic Double Auctions: Towards First Best2019
Efficient Algorithms and Lower Bounds for Robust Linear Regression2019
Elastic Caching2019
Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty2019
Expander Decomposition and Pruning: Faster, Stronger, and Simpler2019
Fast greedy for linear matroids2019
Fast Modular Subset Sum using Linear Sketching2019
Finding a latent k-simplex in O(k . nnz(data)) time via Subset Smoothing2019
Fine-grained Complexity Meets IP = PSPACE2019
Flow-Cut Gaps and Face Covers in Planar Graphs2019
Foundations of Differentially Oblivious Algorithms2019
Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability2019
Fully Dynamic Maximal Independent Set with Sublinear in n Update Time2019
Fully Polynomial-Time Approximation Schemes for Fair Rent Division2019
Hardness of Approximation for Morse Matching2019
Hierarchical Clustering better than Average-Linkage2019
High-Dimensional Robust Mean Estimation in Nearly-Linear Time2019
Improved Bounds for Randomly Sampling Colorings via Linear Programming2019
Improved Topological Approximations by Digitization2019
Interval Vertex Deletion Admits a Polynomial Kernel2019
I/O-Efficient Algorithms for Topological Sort and Related Problems2019
Iterative Refinement for ℓp-norm Regression2019
k-Servers with a Smile: Online Algorithms via Projections2019
Lift and Project Algorithms for Precedence Constrained Scheduling to Minimize Completion Time2019
List Decoding with Double Samplers2019
Losing Treewidth by Separating Subsets2019
Lower Bounds for Oblivious Data Structures2019
Lower bounds for text indexing with mismatches and differences2019
Massively Parallel Approximation Algorithms for Edit Distance and Longest Common Subsequence2019
Maximally Recoverable LRCs: A field size lower bound and constructions for few heavy parities2019
Metrical task systems on trees via mirror descent and unfair gluing2019
Minimum Cut and Minimum k-Cut in Hypergraphs via Branching Contractions2019

« prev Page 14/41 next »