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
A o(d) · polylog n Monotonicity Tester for Boolean Functions over the Hypergrid [n].d2018
A o(d) · polylog n Monotonicity Tester for Boolean Functions over the Hypergrid [n]d2018
A() · polylogMonotonicity Tester for Boolean Functions over the Hypergrid []2018
A Polynomial Excluded-Minor Approximation of Treedepth2018
Approximate Positive Correlated Distributions and Approximation Algorithms for D-optimal Design2018
Approximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spanners2018
Approximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spanners.2018
Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce2018
Approximating the Largest Root and Applications to Interlacing Families2018
Approximating the Nash Social Welfare with Budget-Additive Valuations2018
A Two-pronged Progress in Structured Dense Matrix Vector Multiplication2018
A Two-pronged Progress in Structured Dense Matrix Vector Multiplication.2018
Average-radius list-recoverability of random linear codes2018
Average-radius list-recoverability of random linear codes.2018
Cache-Oblivious and Data-Oblivious Sorting and Applications2018
Cliquewidth III: The Odd Case of Graph Coloring Parameterized by Cliquewidth2018
Community Detection on Euclidean Random Graphs2018
Competitive Algorithms for Generalized k-Server in Uniform Metrics2018
Computing the Independence Polynomial: from the Tree Threshold down to the Roots2018
Consensus of Interacting Particle Systems on Erdös-Rényi Graphs2018
Consistent Hashing with Bounded Loads2018
Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms2018
Cycles in Adversarial Regularized Learning2018
Dichotomy for Real Holantc Problems2018
Dichotomy for Real HolantProblems2018
Discrete Choice, Permutations, and Reconstruction2018
Dynamic Algorithms for Graph Coloring2018
Efficient Õ(n/∊) Spectral Sketches for the Laplacian and its Pseudoinverse2018
Envy-free Chore Division for An Arbitrary Number of Agents2018
Estimating Graph Parameters from Random Order Streams2018
Fast, Deterministic and Sparse Dimensionality Reduction2018
From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games2018
Geometric Rescaling Algorithms for Submodular Function Minimization2018
Hierarchical Clustering: Objective Functions and Algorithms2018
Improved Bounds for Testing Forbidden Order Patterns2018
Improved Coresets for Kernel Density Estimates2018
Kirchhoff Index as a Measure of Edge Centrality in Weighted Networks: Nearly Linear Time Algorithms2018
Lower Bounds for Symbolic Computation on Graphs: Strongly Connected Components, Liveness, Safety, and Diameter2018
Metric Violation Distance: Hardness and Approximation2018
Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities2018
Nearly Tight Bounds for Sandpile Transience on the Grid2018
Nested Convex Bodies are Chaseable2018
Non interactive simulation of correlated distributions is decidable2018
On Simultaneous Two-player Combinatorial Auctions2018
On the Competition Complexity of Dynamic Mechanism Design2018
On the complexity of range searching among curves2018
On the Complexity of Simple and Optimal Deterministic Mechanisms for an Additive Buyer2018
Optimal Dynamic Strings2018
Optimal streaming and tracking distinct elements with high probability2018
Optimal Vertex Fault Tolerant Spanners (for fixed stretch)2018

« prev Page 16/41 next »