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
Submodular Maximization with Cardinality Constraints2014
Testing equivalence between distributions using conditional samples2014
The Complexity of Optimal Mechanism Design2014
The Complexity of Optimal Multidimensional Pricing2014
Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)2014
Towards (1 + ∊)-Approximate Flow Sparsifiers2014
(1+ Є)-approximation for facility location in data streams2013
4-connected projective-planar graphs are hamiltonian-connected2013
5-coloring K3, k-minor-free graphs: Beyond Thomassen2013
An Almost Optimal Algorithm for Computing Nonnegative Rank2013
A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio2013
Approximate Counting via Correlation Decay on Planar Graphs2013
Approximate Maximum Flow on Separable Undirected Graphs2013
Approximating Non-Uniform Sparsest Cut Via Generalized Spectra2013
A Simple Algorithm for the Graph Minor Decomposition - Logic meets Structural Graph Theory2013
Balls into Bins via Local Search2013
Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching2013
Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection2013
Better bounds for matchings in the streaming model2013
Clinching Auction with Online Supply2013
Clustering Affine Subspaces: Hardness and Algorithms2013
Computing the Discrete Fréchet Distance in Subquadratic Time2013
Convergence of multivariate belief propagation, with applications to cuckoo hashing and load balancing2013
Correlation Decay up to Uniqueness in Spin Systems2013
Dichotomy for Holant* Problems with Domain Size 32013
Efficient protocols of generating bipartite classical distributions and quantum states2013
Eigenvalues of a matrix in the streaming model2013
Energy Efficient Scheduling of Parallelizable Jobs2013
Euclidean spanners in high dimensions2013
Fast Algorithms for Interactive Coding2013
Finding Endogenously Formed Communities2013
Higher-Order Geodesic Voronoi Diagrams in a Polygonal Domain with Holes2013
How to Sell Hyperedges: The Hypermatching Assignment Problem2013
Known algorithms for EDGE CLIQUE COVER are probably optimal2013
Learning Disjunctions: Near-Optimal Trade-off between Mistakes and "I Don't Know's"2013
Learning mixtures of structured distributions over discrete domains2013
Learning pseudo-Boolean k-DNF and submodular functions2013
List-coloring embedded graphs2013
Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems2013
Local-Search based Approximation Algorithms for Mobile Facility Location Problems2013
Low-distortion Inference of Latent Similarities from a Multiplex Social Network2013
Lower Bounds for Adaptive Sparse Recovery2013
Matroid Secretary for Regular and Decomposable Matroids2013
Mimicking Networks and Succinct Representations of Terminal Cuts2013
Minimum Makespan Scheduling with Low Rank Processing Times2013
More Compact Oracles for Approximate Distances in Undirected Planar Graphs2013
Morphing Planar Graph Drawings with a Polynomial Number of Steps2013
Near-Optimal Range Reporting Structures for Categorical Data2013
On differentially private low rank approximation2013
Online Mixed Packing and Covering2013

« prev Page 24/41 next »