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 Stochastic Matching with Unequal Probabilities2015
Online Submodular Maximization with Preemption2015
On the Complexity of Computing an Equilibrium in Combinatorial Auctions2015
On the Quickest Flow Problem in Dynamic Networks - A Parametric Min-Cost Flow Approach2015
On Uniform Capacitated k-Median Beyond the Natural LP Relaxation2015
Optimal approximation for submodular and supermodular optimization with bounded curvature2015
Parameterized Streaming: Maximal Matching and Vertex Cover2015
Perfect Bayesian Equilibria in Repeated Sales2015
Plurality Consensus in the Gossip Model2015
Pricing Online Decisions: Beyond Auctions2015
Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties2015
Rejecting jobs to Minimize Load and Maximum Flow-time2015
Revealing Optimal Thresholds for Generalized Secretary Problem via Continuous LP: Impacts on Online K-Item Auction and Bipartite K-Matching with Random Arrival Order2015
Robust Price of Anarchy Bounds via LP and Fenchel Duality2015
Robust Probabilistic Inference2015
Sequential Random Permutation, List Contraction and Tree Contraction are Highly Parallel2015
Sketching for M-Estimators: A Unified Approach to Robust Regression2015
Spider covers for prize-collecting network activation problem2015
Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond2015
Streaming Lower Bounds for Approximating MAX-CUT2015
Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs2015
Testing Identity of Structured Distributions2015
Testing Poisson Binomial Distributions2015
The amortized cost of finding the minimum2015
The Complexity of Estimating Rényi Entropy2015
The matching polytope does not admit fully-polynomial size relaxation schemes2015
The Speed of Evolution2015
The Value 1 Problem Under Finite-memory Strategies for Concurrent Mean-payoff Games2015
Tighter Low-rank Approximation via Sampling the Leveraged Element2015
Using Optimization to Break the Epsilon Barrier: A Faster and Simpler Width-Independent Algorithm for Solving Positive Linear Programs in Parallel2015
Zigzag Persistence via Reflections and Transpositions2015
A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median2014
A constructive algorithm for the Lovász Local Lemma on permutations2014
A Cubic Algorithm for Computing Gaussian Volume2014
A Mazing 2+∊ Approximation for Unsplittable Flow on a Path2014
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations2014
Analyzing the Optimal Neighborhood: Algorithms for Budgeted and Partial Connected Dominating Set Problems2014
An Excluded Grid Theorem for Digraphs with Forbidden Minors2014
Annotations for Sparse Data Streams2014
An Optimal Lower Bound for Distinct Elements in the Message Passing Model2014
A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage2014
Approximating Local Homology from Samples2014
Approximating matching size from random streams2014
Approximating Minimum Cost Connectivity Orientation and Augmentation2014
Approximation Algorithm for Sparsest k-Partitioning2014
Approximation-Tolerant Model-Based Compressive Sensing2014
A Simple FPTAS for Counting Edge Covers2014
A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths2014
Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach2014
Better Approximation Algorithms for the Graph Diameter2014

« prev Page 22/41 next »