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
On the power of two, three and four probes2009
Optimal halfspace range reporting in three dimensions2009
Optimality of belief propagation for random assignment problem2009
Overcoming the l1 non-embeddability barrier: algorithms for product metrics2009
Packing multiway cuts in capacitated graphs2009
Paging and list update under bijective analysis2009
Partitioning graphs into balanced components2009
Perfect matchings via uniform sampling in regular bipartite graphs2009
Persistent homology for kernels, images, and cokernels2009
Secretary problems: weights and discounts2009
Sequential cavity method for computing limits of the log-partition function for lattice models2009
Size complexity of volume meshes vs. surface meshes2009
Sorting and selection in posets2009
Stepwise randomized combinatorial auctions achieve revenue monotonicity2009
Stream sampling for variance-optimal estimation of subset sums2009
Termination criteria for solving concurrent safety and reachability games2009
The geometry of binary search trees2009
The uniform hardcore lemma via approximate Bregman projections2009
Three-coloring triangle-free planar graphs in linear time2009
Towards computing the Grothendieck constant2009
Transitive-closure spanners2009
(Un)expected behavior of digital search tree profile2009
Algorithms for distributed functional monitoring2008
(Almost) optimal coordination mechanisms for unrelated machine scheduling2008
A nearly linear time algorithm for the half integral disjoint paths packing2008
A plant location guide for the unsure2008
Approximating TSP on metrics with bounded global growth2008
Auctions for structured procurement2008
Better bounds for online load balancing on unrelated machines2008
Competitive queue management for latency sensitive packets2008
Computing excluded minors2008
Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm2008
Declaring independence via the sketching of sketches2008
Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles2008
Designing networks with good equilibria2008
Deterministic random walks on regular trees2008
Earth mover distance over high-dimensional spaces2008
Estimators and tail bounds for dimension reduction in lα (0 < α ≤ 2) using stable random projections2008
Exact and efficient 2D-arrangements of arbitrary algebraic curves2008
Explicit constructions for compressed sensing of sparse signals2008
Fast asynchronous byzantine agreement and leader election with full information2008
Fast dimension reduction using Rademacher series on dual BCH codes2008
Fast edge splitting and Edmonds' arborescence construction for unweighted graphs2008
Fast load balancing via bounded best response2008
Fully polynomial time approximation schemes for stochastic dynamic programs2008
Geodesic Delaunay triangulation and witness complex in the plane2008
Graph algorithms for biological systems analysis2008
Holographic algorithms with unsymmetric signatures2008
Improved algorithmic versions of the Lovász Local Lemma2008
Improved algorithms for fully dynamic geometric spanners and geometric routing2008

« prev Page 30/41 next »