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
Erdös-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing2012
Fast zeta transforms for lattices with few irreducibles2012
Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset2012
Inapproximability of the multi-level uncapacitated facility location problem2012
Information dissemination via random walks in d-dimensional space2012
I/O-efficient data structures for colored range and prefix reporting2012
Learning k-modal distributions via testing2012
List-coloring graphs without subdivisions and without immersions2012
Local homology transfer and stratification learning2012
Lower bounds for number-in-hand multiparty communication complexity, made easy2012
LSH-preserving functions and their applications2012
Mechanism design via consensus estimates, cross checking, and profit extraction2012
Metastability of logit dynamics for coordination games2012
Networks cannot compute their diameter in sublinear time2012
Online scheduling with general cost functions2012
On the communication and streaming complexity of maximum bipartite matching2012
Optimal column-based low-rank matrix reconstruction2012
Optimal crowdsourcing contests2012
Physarum can compute shortest paths2012
Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph2012
Privacy-preserving group data access via stateless oblivious RAM simulation2012
Private data release via learning thresholds2012
Race to idle: new algorithms for speed scaling with a sleep state2012
Resource augmentation for weighted flow-time explained by dual fitting2012
Scheduling heterogeneous processors isn't as easy as you think2012
Sequential auctions and externalities2012
Simple and practical algorithm for sparse Fourier transform2012
Simultaneous approximations for adversarial and stochastic online budgeted allocation2012
Sketching valuation functions2012
Space-efficient local computation algorithms2012
Spanning closed walks and TSP in 3-connected planar graphs2012
Sparser Johnson-Lindenstrauss transforms2012
Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications2012
Submodular functions are noise stable2012
The condensation transition in random hypergraph 2-coloring2012
The set of solutions of random XORSAT formulae2012
The shifting sands algorithm2012
Towards robust and efficient computation in dynamic peer-to-peer networks2012
Traffic-redundancy aware network design2012
Voting with limited information and many alternatives2012
Weak compositions and their applications to polynomial lower bounds for kernelization2012
Width of points in the streaming model2012
A Constant-Factor Approximation for Wireless Capacity Maximization with Power Control in the SINR Model2011
Algorithms and Hardness for Subspace Approximation2011
Algorithms for Implicit Hitting Set Problems2011
A Master Theorem for Discrete Divide and Conquer Recurrences2011
An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform2011
A Nonlinear Approach to Dimension Reduction2011
Approximate Dynamic Programming using Halfspace Queries and Multiscale Monge Decomposition2011
Approximating Matrix p-norms2011

« prev Page 26/41 next »