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
Designing and learning optimal finite support auctions2007
Efficient aggregation algorithms for probabilistic data2007
Efficient algorithms for computing all low s-t edge connectivities and related problems2007
Efficient contention resolution protocols for selfish agents2007
Estimating the sortedness of a data stream2007
Faster dynamic matchings and vertex connectivity2007
Half integral packing, Erdős-Posá-property and graph minors2007
Harmonic algorithm for 3-dimensional strip packing problem2007
Improved bounds for the online steiner tree problem in graphs of bounded edge-asymmetry2007
k-means++: the advantages of careful seeding2007
Line-of-sight networks2007
Matroids, secretary problems, and online mechanisms2007
Minimizing movement2007
Multiple choice tries and distributed hash tables2007
Near-optimal algorithms for maximum constraint satisfaction problems2007
Noisy binary search and its applications2007
On Bregman Voronoi diagrams2007
On the separation and equivalence of paging strategies2007
Optimal dynamic vertical ray shooting in rectilinear planar subdivisions2007
Reconstruction using witness complexes2007
Restricted strip covering and the sensor cover problem2007
Scrambling adversarial errors using few random bits, optimal information reconciliation, and better private codes2007
Semi-oblivious routing: lower bounds2007
Spectral clustering with limited independence2007
Speed scaling for weighted flow time2007
Strong price of anarchy2007
The approximation complexity of win-lose games2007
The communication and streaming complexity of computing the longest common and increasing subsequences2007
Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP: extended abstract2007
A general approach for incremental approximation and hierarchical clustering2006
Analysis of incomplete data and an intrinsic-dimension Helly theorem2006
Analyzing BitTorrent and related peer-to-peer networks2006
A near-tight approximation lower bound and algorithm for the kidnapped robot problem2006
Anytime algorithms for multi-armed bandit problems2006
Approximating unique games2006
A robust maximum completion time measure for scheduling2006
A semidefinite programming approach to tensegrity theory and realizability of graphs2006
Balanced allocation on graphs2006
Bottleneck links, variable demand, and the tragedy of the commons2006
Combination can be hard: approximability of the unique coverage problem2006
Computing steiner minimum trees in Hamming metric2006
Constraint solving via fractional edge covers2006
Counting without sampling: new algorithms for enumeration problems using statistical physics2006
Directed metrics and directed graph partitioning problems2006
Efficient algorithms for substring near neighbor problem2006
Entropy based nearest neighbor search in high dimensions2006
Finding nucleolus of flow game2006
Improved approximation algorithms for broadcast scheduling2006
Improved embeddings of graph metrics into random trees2006
Improved lower and upper bounds for universal TSP in planar metrics2006

« prev Page 32/41 next »