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 and Random-order Load Balancing Simultaneously2017
Online Lower Bounds via Duality2017
Online Submodular Maximization with Free Disposal: Randomization Beats ¼ for Partition Matroids2017
On Rationality of Nonnegative Matrix Factorization2017
Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors2017
Optimal induced universal graphs for bounded-degree graphs2017
Opting Into Optimal Matchings2017
Parameter-free Locality Sensitive Hashing for Spherical Range Reporting2017
Parameter-free Topology Inference and Sparsification for Data on Manifolds2017
Partitioning a Graph into Small Pieces with Applications to Path Transversal2017
Playing Anonymous Games using Simple Strategies2017
Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays2017
Proximity in the Age of Distraction: Robust Approximate Nearest Neighbor Search2017
Random Contractions and Sampling for Hypergraph and Hedge Connectivity2017
Reordering Buffers with Logarithmic Diameter Dependency for Trees2017
Robust algorithms with polynomial loss for near-unanimity CSPs2017
Sample-Optimal Density Estimation in Nearly-Linear Time2017
Simplex Transformations and the Multiway Cut Problem2017
Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits2017
Sorting from Noisier Samples2017
Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization2017
Stochastic k-Center and j-Flat-Center Problems2017
Strong Connectivity in Directed Graphs under Failures, with Applications2017
The (h, k)-Server Problem on Bounded Depth Trees2017
Tight Network Topology Dependent Bounds on Rounds of Communication2017
Tight Network Topology Dependent Bounds on Rounds of Communication.2017
Time-Space Trade-offs in Population Protocols2017
Totally Unimodular Congestion Games2017
Unrelated Machine Scheduling of Jobs with Uniform Smith Ratios2017
A Fast Approximation for Maximum Weight Matroid Intersection2016
Algorithmic and Enumerative Aspects of the Moser-Tardos Distribution2016
Algorithmic Complexity of Power Law Networks2016
Algorithms and Adaptivity Gaps for Stochastic Probing2016
An Improved Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market2016
An O(log m)-Competitive Algorithm for Online Machine Minimization2016
Approximately Efficient Double Auctions with Strong Budget Balance2016
Approximating capacitated k-median with (1 + ∊)k open facilities2016
Approximating Low-Stretch Spanners2016
Approximating the k-Level in Three-Dimensional Plane Arrangements2016
Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs2016
Bounds for Random Constraint Satisfaction Problems via Spatial Coupling2016
Canonical Paths for MCMC: from Art to Science2016
Canonical Paths for MCMC: from Art to Science.2016
Clustering Problems on Sliding Windows2016
Clustering time series under the Fréchet distance2016
Communication Complexity of Permutation-Invariant Functions2016
Communication with Contextual Uncertainty2016
Constant Factor Approximation for Subset Feedback Set Problems via a new LP relaxation2016
Designing Networks with Good Equilibria under Uncertainty2016
Deterministic Algorithms for Submodular Maximization Problems2016

« prev Page 19/41 next »