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
Online Multiserver Convex Chasing and Optimization2021
On Multi-Dimensional Gains from Trade Maximization2021
On Testability of First-Order Properties in Bounded-Degree Graphs2021
On the Competitive Analysis and High Accuracy Optimality of Profile Maximum Likelihood2021
On the Orbit Closure Containment Problem and Slice Rank of Tensors2021
On Tolerant Distribution Testing in the Conditional Sampling Model2021
On Two-Handed Planar Assembly Partitioning with Connectivity Constraints2021
Optimal Contextual Pricing and Extensions2021
Optimal Discretization is Fixed-parameter Tractable2021
Optimal Inapproximability with Universal Factor Graphs2021
Optimal ℓ1 Column Subset Selection and a Fast PTAS for Low Rank Approximation2021
Optimal Oblivious Priority Queues2021
Optimal Vertex Fault-Tolerant Spanners in Polynomial Time2021
Planar Reachability Under Single Vertex or Edge Failures2021
Polyhedral Value Iteration for Discounted Games and Energy Games2021
PTAS for Minimum Cost Multi-covering with Disks2021
Quantum algorithms for graph problems with cut queries2021
Query strategies for priced information, revisited2021
Random Restrictions of High Dimensional Distributions and Uniformity Testing with Subcube Conditioning2021
Rapid Mixing from Spectral Independence beyond the Boolean Domain2021
Robust Algorithms for Online Convex Problems via Primal-Dual2021
Robust Learning of Mixtures of Gaussians2021
Scheduling with Communication Delays via LP Hierarchies and Clustering II: Weighted Completion Times on Related Machines2021
Shortest Paths Among Obstacles in the Plane Revisited2021
Solving Sparse Linear Systems Faster than Matrix Multiplication2021
SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation2021
Space Lower Bounds for Approximating Maximum Matching in the Edge Arrival Model2021
Spectral Clustering Oracles in Sublinear Time2021
Static and Streaming Data Structures for Fréchet Distance Queries2021
Streaming Submodular Matching Meets the Primal-Dual Method2021
The Connectivity Threshold for Dense Graphs2021
The Demand Query Model for Bipartite Matching2021
The Expander Hierarchy and its Applications to Dynamic Graph Algorithms2021
The Min-Cost Matching with Concave Delays Problem2021
The Secretary Problem with Independent Sampling2021
Tight Bounds for Online Graph Partitioning2021
Towards PTAS for Precedence Constrained Scheduling via Combinatorial Algorithms2021
Treewidth-Pliability and PTAS for Max-CSPs2021
Two-stage Stochastic Matching with Application to Ride Hailing2021
Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers2021
Uncertainty about Uncertainty: Optimal Adaptive Algorithms for Estimating Mixtures of Unknown Coins2021
Vertex Sparsification for Edge Connectivity2021
A Deterministic Linear Program Solver in Current Matrix Multiplication Time2020
A face cover perspective to ℓ1 embeddings of planar graphs2020
Algorithmic Price Discrimination2020
A Little Charity Guarantees Almost Envy-Freeness2020
A Lower Bound for Jumbled Indexing2020
A nearly 5/3-approximation FPT Algorithm for Min-k-Cut2020
An Improved Algorithm for Incremental Cycle Detection and Topological Ordering in Sparse Graphs2020
An Õ(n5/4) Time ε-Approximation Algorithm for RMS Matching in a Plane2020

« prev Page 11/41 next »