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
Improved algorithms for orienteering and related problems2008
Incentive compatible regression learning2008
Linked decompositions of networks and the power of choice in Polya urns2008
Matroid intersection, pointer chasing, and Young's seminormal representation of S.n2008
Matroid intersection, pointer chasing, and Young's seminormal representation of Sn2008
Metric clustering via consistent labeling2008
Noisy sorting without resampling2008
On distributing symmetric streaming computations2008
Online budgeted matching in random input models with applications to Adwords2008
Online make-to-order joint replenishment model: primal dual competitive algorithms2008
Optimal universal graphs with deterministic embedding2008
Parallel monotonicity reconstruction2008
Provably good multicore cache performance for divide-and-conquer algorithms2008
Quasirandom rumor spreading2008
Rapid mixing of Gibbs sampling on graphs that are sparse on average2008
Robust cost colorings2008
Sampling algorithms and coresets for ℓp regression2008
Sampling algorithms and coresets for ℓregression2008
Set connectivity problems in undirected graphs and the directed Steiner network problem2008
Stochastic analyses for online combinatorial optimization problems2008
Succinct approximate convex pareto curves2008
The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond2008
The hiring problem and Lake Wobegon strategies2008
Tight lower bounds for selection in randomly ordered streams2008
Trace reconstruction with constant deletion probability and related results2008
Ultra-low-dimensional embeddings for doubling metrics2008
Weak ε-nets and interval chains2008
Why simple hash functions work: exploiting the entropy in a data stream2008
A divide and conquer algorithm for d-dimensional arrangement2007
Aggregation of partial rankings, p-ratings and top-m lists2007
A linear work, O(n1/6) time, parallel algorithm for solving planar Laplacians2007
A lower bound for scheduling mechanisms2007
An algebraic algorithm for weighted linear matroid intersection2007
A near linear time constant factor approximation for Euclidean bichromatic matching (cost)2007
A near-optimal algorithm for computing the entropy of a stream2007
An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem2007
An elementary construction of constant-degree expanders2007
Approximation algorithms for embedding general metrics into trees2007
Approximation algorithms for node-weighted buy-at-bulk network design2007
Approximation algorithms for stochastic and risk-averse optimization2007
Approximation algorithms via contraction decomposition2007
A rigorous analysis of population stratification with limited data2007
Better online buffer management2007
Buying cheap is expensive: hardness of non-parametric multi-product pricing2007
Combinatorial algorithms for web search engines: three success stories2007
Compressing rectilinear pictures and minimizing access control lists2007
Considering suppressed packets improves buffer management in QoS switches2007
Correlation decay and deterministic FPTAS for counting list-colorings of a graph2007
Counting colors in boxes2007
Counting good truth assignments of random k-SAT formulae2007

« prev Page 31/41 next »