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
A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover2010
A Deterministic Truthful PTAS for Scheduling Related Machines2010
A Fourier Space Algorithm for Solving Quadratic Assignment Problems2010
Algorithms and Complexity for Periodic Real-Time Scheduling2010
A Model of Computation for MapReduce2010
An (almost) Linear Time Algorithm for Odd Cyles Transversal2010
An Online Scalable Algorithm for Average Flow Time in Broadcast Scheduling2010
A QPTAS for TSP with Fat Weakly Disjoint Neighborhoods in Doubling Metrics2010
A Space-Time Tradeoff for Permutation Problems2010
Belief Propagation for Min-cost Network Flow: Convergence & Correctness2010
Convergence, Stability, and Discrete Approximation of Laplace Spectra2010
Coresets and Sketches for High Dimensional Subspace Approximation Problems2010
Correlation Robust Stochastic Optimization2010
Decomposition, Approximation, and Coloring of Odd-Minor-Free Graphs2010
Deletion Without Rebalancing in Balanced Binary Trees2010
Deterministic Algorithms for the Lovász Local Lemma2010
Differentially Private Combinatorial Optimization2010
Distributed Agreement with Optimal Communication Complexity2010
Efficiently Decodable Non-adaptive Group Testing2010
Fast SDP Algorithms for Constraint Satisfaction Problems2010
Finding the Jaccard Median2010
Flow-Cut Gaps for Integer and Fractional Multiflows2010
Google's Auction for TV Ads2010
Hardness Results for Homology Localization2010
How Good is the Chord Algorithm?2010
Improved Approximation Algorithms for the Minimum Latency Problem via Prize-Collecting Strolls2010
Inapproximability for VCG-Based Combinatorial Auctions2010
Incentive Compatible Budget Elicitation in Multi-unit Auctions2010
Lower Bounds for Edit Distance and Product Metrics via Poincaré-Type Inequalities2010
Lower Bounds for Sparse Recovery2010
Lower Bounds for Testing Triangle-freeness in Boolean Functions2010
Monotonicity in Bargaining Networks2010
Near-Optimal Sublinear Time Algorithms for Ulam Distance2010
Online Learning with Queries2010
On the Cell Probe Complexity of Dynamic Membership2010
On the Equilibria of Alternating Move Games2010
On the Exact Space Complexity of Sketching and Streaming Small Norms2010
Optimally Reconstructing Weighted Graphs Using Queries2010
Price of Anarchy for Greedy Auctions2010
Pricing Randomized Allocations2010
Probabilistic Analysis of the Semidefinite Relaxation Detector in Digital Communications2010
PTAS for Maximum Weight Independent Set Problem with Random Weights in Bounded Degree Graphs2010
Recognizing a Totally Odd K4-subdivision, Parity 2-disjoint Rooted Paths and a Parity Cycle Through Specified Elements2010
Region Growing for Multi-Route Cuts2010
Road Network Reconstruction for Organizing Paths2010
Rumour Spreading and Graph Conductance2010
Self-improving Algorithms for Convex Hulls2010
Sharp Dichotomies for Regret Minimization in Metric Spaces2010
Solving MAX-r-SAT Above a Tight Lower Bound2010
Streaming Algorithms for Extent Problems in High Dimensions2010

« prev Page 28/41 next »