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
Approximate Maximum Matching in Random Streams2020
Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings2020
Approximating the Distance to Monotonicity of Boolean Functions2020
Approximation Schemes for Capacitated Clustering in Doubling Metrics2020
Approximation Schemes via Width/Weight Trade-offs on Minor-free Graphs2020
A PTAS for subset TSP in minor-free graphs2020
A Tale of Santa Claus, Hypergraphs and Matroids2020
A Tight Analysis of Greedy Yields Subexponential Time Approximation for Uniform Decision Tree2020
A Truthful Cardinal Mechanism for One-Sided Matching2020
Bulow-Klemperer-Style Results for Welfare Maximization in Two-Sided Markets2020
Cake Cutting on Graphs: A Discrete and Bounded Proportional Protocol2020
Chasing Convex Bodies Optimally2020
Chasing Convex Bodies with Linear Competitive Ratio2020
Chasing Nested Convex Bodies Nearly Optimally2020
Coarse-Grained Complexity for Dynamic Algorithms2020
Competitive Analysis with a Sample and the Secretary Problem2020
Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Block Laplacians2020
Composable Core-sets for Determinant Maximization Problems via Spectral Spanners2020
Computational Concentration of Measure: Optimal Bounds, Reductions, and More2020
Computing Circle Packing Representations of Planar Graphs2020
Differentially Private Release of Synthetic Graphs2020
Domain Reduction for Monotonicity Testing: A o(d) Tester for Boolean Functions in d-Dimensions2020
Efficiency of the floating body as a robust measure of dispersion2020
Efficiently list-edge coloring multigraphs asymptotically optimally2020
Equivalences between triangle and range query problems2020
Exact computation of a manifold metric, via Lipschitz Embeddings and Shortest Paths on a Graph2020
Exponential Separations in Local Differential Privacy2020
Extended Formulation Lower Bounds for Refuting Random CSPs2020
Fast and Space Efficient Spectral Sparsification in Dynamic Streams2020
Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions2020
Faster p-norm minimizing flows, via smoothed q-norm problems2020
Faster sublinear approximation of the number of k-cliques in low-arboricity graphs2020
Faster Update Time for Turnstile Streaming Algorithms2020
Fast LP-based Approximations for Geometric Packing and Covering Problems2020
Finding a Bounded-Degree Expander Inside a Dense One2020
Finding a latent k-simplex in O* (k · nnz(data)) time via Subset Smoothing2020
Fully Dynamic Matching: Beating 2-Approximation in Δ Update Time.ϵ2020
Fully Dynamic Matching: Beating 2-Approximation in Δϵ Update Time2020
Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints2020
How to aggregate Top-lists: Approximation algorithms via scores and average ranks2020
Improved Algorithms for Edit Distance and LCS: Beyond Worst Case2020
Improved Local Computation Algorithm for Set Cover via Sparsification2020
Individual Sensitivity Preprocessing for Data Privacy2020
Inference from Auction Prices2020
Instance-Optimality in the Noisy Value-and Comparison-Model2020
Interleaved Caching with Access Graphs2020
Labelings vs. Embeddings: On Distributed Representations of Distances2020
Learning from satisfying assignments under continuous distributions2020
Locally Private k-Means Clustering2020
Lower Bounds for Oblivious Near-Neighbor Search2020

« prev Page 12/41 next »