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
Subtree Isomorphism Revisited2016
The Adversarial Noise Threshold for Distributed Protocols2016
The Complexity of All-switches Strategy Improvement2016
The matching problem has no small symmetric SDP2016
Tight Bounds for Graph Homomorphism and Subgraph Isomorphism2016
Towards Optimal Algorithms for Prediction with Expert Advice2016
Undirected Graph Exploration with ⊝(log log n) Pebbles2016
Undirected Graph Exploration with ⊝(log log) Pebbles2016
Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver2016
Weighted SGD for ℓp Regression with Randomized Preconditioning2016
Weighted SGD for ℓ Regression with Randomized Preconditioning.p2016
Weighted SGD forRegression with Randomized Preconditioning2016
A dynamic model of barter exchange2015
A Dynamic Programming Framework for Non-Preemptive Scheduling Problems on Multiple Machines [Extended Abstract]2015
A Fully Polynomial-Time Approximation Scheme for Speed Scaling with Sleep State2015
Algorithmic regularity for polynomials and applications2015
An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization2015
An n-to-1 Bidder Reduction for Multi-item Auctions and its Applications2015
Approximately Stable, School Optimal, and Student-Truthful Many-to-One Matchings (via Differential Privacy)2015
Approximate Nearest Line Search in High Dimensions2015
Approximate Range Emptiness in Constant Time and Optimal Space2015
Approximate resilience, monotonicity, and the complexity of agnostic learning2015
Approximating Hereditary Discrepancy via Small Width Ellipsoids2015
A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem2015
A Stable Marriage Requires Communication2015
A Unified Framework for Clustering Constrained Data without Locality Property2015
Bayesian Truthful Mechanisms for Job Scheduling from Bi-criterion Approximation Algorithms2015
Combinatorial Algorithm for Restricted Max-Min Fair Allocation2015
Combinatorial Auctions via Posted Prices2015
Comparing Apples and Oranges: Query Tradeoff in Submodular Maximization2015
Connectivity in Random Forests and Credit Networks2015
Contagious Sets in Expanders2015
Degree-3 Treewidth Sparsifiers2015
Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching2015
Dynamic Facility Location via Exponential Clocks2015
Efficient and Robust Persistent Homology for Measures2015
Fast Algorithms for Online Stochastic Convex Programming2015
Fast Generation of Random Spanning Trees and the Effective Resistance Metric2015
Finding Four-Node Subgraphs in Triangle Time2015
FPTAS for Counting Monotone CNF2015
Gossip vs. Markov Chains, and Randomness-Efficient Rumor Spreading2015
Improved Region-Growing and Combinatorial Algorithms for k-Route Cut Problems (Extended Abstract)2015
Learning from satisfying assignments2015
Learning Privately with Labeled and Unlabeled Examples2015
Limitations on Testable Affine-Invariant Codes in the High-Rate Regime2015
LP/SDP Hierarchy Lower Bounds for Decoding Random LDPC Codes2015
New Approximation Schemes for Unsplittable Flow on a Path2015
New Approximations for Broadcast Scheduling via Variants of α-point Rounding2015
On (1, ∊)-Restricted Assignment Makespan Minimization2015
Online Principal Components Analysis2015

« prev Page 21/41 next »