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
Efficient algorithms for bichromatic separability2004
Efficient estimation algorithms for neighborhood variance and other moments2004
Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates2004
End-to-end packet-scheduling in wireless ad-hoc networks2004
Equivalence of local treewidth and linear local treewidth and its algorithmic applications2004
Family trees: an ordered dictionary with optimal congestion, locality, degree, and search time2004
Fast approximate pattern matching with few indels via embeddings2004
Frugality in path auctions2004
Improved bounds on sorting with length-weighted reversals2004
Linear phase transition in random linear constraint satisfaction problems2004
Matrix rounding and approximation2004
Minimizing migrations in fair multiprocessor scheduling of persistent tasks2004
Multicommodity facility location2004
Navigating nets: simple algorithms for proximity search2004
Network failure detection and graph connectivity2004
New approximability and inapproximability results for 2-dimensional Bin Packing2004
On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems2004
Optimal space lower bounds for all frequency moments2004
Point containment in the integer hull of a polyhedron2004
Quantitative stochastic parity games2004
Randomized pursuit-evasion with limited visibility2004
Rank-maximal matchings2004
Reconstructing strings from random traces2004
Structural and algorithmic aspects of massive social networks2004
Subexponential parameterized algorithms on graphs of bounded-genus and H-minor-free graphs2004
The Bloomier filter: an efficient data structure for static support lookup tables2004
The maximum latency of selfish routing2004
The wake-up problem in multi-hop radio networks2004
Algorithms for power savings2003
A new approximation algorithm for the asymmetric TSP with triangle inequality2003
An improved approximation algorithm for the 0-extension problem2003
An improved approximation algorithm for the partial latin square extension problem2003
A note on the set systems used for broadcast encryption2003
Approximating asymmetric maximum TSP2003
Better algorithms for high-dimensional proximity problems via asymmetric embeddings2003
Certifying algorithms for recognizing interval graphs and permutation graphs2003
Certifying and repairing solutions to large LPs how good are LP-solvers?2003
Comparing top k lists2003
Competitiveness via consensus2003
Competitive queueing policies for QoS switches2003
Counting inversions in lists2003
Deterministic identity testing for multivariate polynomials2003
Edge disjoint paths revisited2003
Efficient sequences of trials2003
Embedding k-outerplanar graphs into l12003
Embeddings and non-approximability of geometric problems2003
Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons2003
Faster approximation algorithms for the minimum latency problem2003
Improved results for directed multicut2003
Inferring tree topologies using flow tests2003

« prev Page 35/41 next »