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
Bayesian Incentive Compatibility via Matchings2011
Capacitated Metric Labeling2011
Computing Shortest Paths amid Pseudodisks2011
Continuous Local Search2011
Dichotomy for Holant* Problems of Boolean Domain2011
Dimensionality reduction: Beyond the Johnson-Lindenstrauss bound2011
Efficient Sketches for the Set Query Problem2011
Fast Convergence of Natural Bargaining Dynamics in Exchange Networks2011
Faster and Dynamic Algorithms for Maximal End-Component Decomposition and Related Graph Problems in Probabilistic Verification2011
Fast, precise and dynamic distance queries2011
Generalized Machine Activation Problems2011
Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions2011
Improved Deterministic Algorithms for Decremental Transitive Closure and Strongly Connected Components2011
Improved Space Bounds for Cache-Oblivious Range Reporting2011
I/O-Efficient Contour Queries on Terrains2011
Local Smoothness and the Price of Anarchy in Atomic Splittable Congestion Games2011
Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding2011
Multicommodity Facility Location under Group Steiner Access Cost2011
New Approximation Algorithms for Minimum Enclosing Convex Shapes.2011
Online Scalable Algorithm for Minimizing ℓk-norms of Weighted Flow Time On Unrelated Machines2011
Online Scalable Scheduling for the ℓk-norms of Flow Time Without Conservation of Work2011
Online Scheduling on Identical Machines using SRPT2011
Online Scheduling on Identical Machines using SRPT.2011
Online Stochastic Matching: Online Actions Based on Offline Statistics2011
Online Vertex-Weighted Bipartite Matching and Single-bid Budgeted Allocations2011
On LP-Based Approximability for Strict CSPs2011
On Minmax Theorems for Multiplayer Games2011
On Parity Check (0, 1)-Matrix over Zp2011
On the Approximability of Budget Feasible Mechanisms2011
Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Sub-Constant Error2011
Ordered and Unordered Top-K Range Reporting in Large Data Sets2011
Prize-collecting Steiner Problems on Planar Graphs2011
Randomized Variants of Johnson's Algorithm for MAX SAT2011
Range Selection and Median: Tight Cell Probe Lower Bounds and Adaptive Data Structures2011
Ranking with Submodular Valuations2011
Secretary Problems: Laminar Matroid and Interval Scheduling2011
Streaming k-means on Well-Clusterable Data2011
Subsampling Mathematical Relaxations and Average-case Complexity2011
Survivable Network Design Problems in Wireless Networks2011
The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus2011
The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number2011
The Matroid Median Problem2011
The Rigidity Transition in Random Graphs2011
The Rigidity Transition in Random Graphs.2011
Tight Hardness Results for Minimizing Discrepancy2011
Towards an SDP-based Approach to Spectral Methods: A Nearly-Linear-Time Algorithm for Graph Partitioning and Decomposition2011
Welfare Guarantees for Combinatorial Auctions with Item Bidding2011
Where computer vision needs help from computer science2011
1-Pass Relative-Error Lp-Sampling with Applications2010
A 1.43-Competitive Online Graph Edge Coloring Algorithm in the Random Order Arrival Model2010

« prev Page 27/41 next »