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
Multi-unit Supply-monotone Auctions with Bayesian Valuations2019
Non-empty Bins with Simple Tabulation Hashing2019
On Approximating (Sparse) Covering Integer Programs2019
On coalescence time in graphs: When is coalescing as fast as meeting?: Extended Abstract2019
On Facility Location with General Lower Bounds2019
On r-Simple k-Path and Related Problems Parameterized by k/r2019
On the discrepancy of random low degree set systems2019
On the Number of Circuits in Regular Matroids (with Connections to Lattices and Codes)2019
Optimal Las Vegas Approximate Near Neighbors in ℓp2019
Optimizing quantum optimization algorithms via faster quantum gradient computation.2019
Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications2019
Polynomial Planar Directed Grid Theorem2019
Polynomial-time Approximation Scheme for Minimum k-cut in Planar and Minor-free Graphs2019
Popular Matching in Roommates Setting is NP-hard2019
Popular Matchings and Limits to Tractability2019
Pricing for Online Resource Allocation: Intervals and Paths2019
Prophet Secretary Through Blind Strategies2019
Pseudorandomness for read-k DNF formulas2019
Quantum algorithms and approximating polynomials for composed functions with shared inputs2019
Relative Error Tensor Low Rank Approximation2019
Seeded Graph Matching via Large Neighborhood Statistics2019
Spectral Sparsification of Hypergraphs2019
Stochastic ℓp Load Balancing and Moment Problems via the L-Function Method2019
Stochastic Matching with Few Queries: New Algorithms and Tools2019
Stochastic Submodular Cover with Limited Adaptivity.2019
Strategies for Stable Merge Sorting2019
Sublinear Algorithms for (Δ + 1) Vertex Coloring2019
Submodular Function Maximization in Parallel via the Multilinear Relaxation2019
Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity2019
Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time2019
Synchronization Strings: Highly Efficient Deterministic Constructions over Small Alphabets2019
Testing Matrix Rank, Optimally2019
The threshold for SDP-refutation of random regular NAE-3SAT2019
Tight Bounds for ℓp Oblivious Subspace Embeddings2019
Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model2019
Tight Revenue Gaps among Simple Mechanisms2019
Towards Instance-Optimal Private Query Release2019
Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games2019
Zeros of Holant problems: locations and algorithms2019
Adaptive Hierarchical Clustering Using Ordinal Queries2018
A Fast Approximation Scheme for Low-Dimensional k-Means2018
A Faster Algorithm for Minimum-Cost Bipartite Perfect Matching in Planar Graphs2018
A Framework for the Secretary Problem on the Intersection of Matroids2018
A Grid-Based Approximation Algorithm for the Minimum Weight Triangulation Problem2018
Algorithms to Approximate Column-Sparse Packing Problems2018
Almost Envy-Freeness with General Valuations2018
A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs with a Fixed Number of Terminals2018
A Nearly Instance Optimal Algorithm for Top-k Ranking under the Multinomial Logit Model2018
A New Class of Combinatorial Markets with Covering Constraints: Algorithms and Applications2018
An FPT Algorithm Beating 2-Approximation for k-Cut2018

« prev Page 15/41 next »