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
Multi-transversals for Triangles and the Tuza's Conjecture2020
Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions2020
Near-optimal Approximate Discrete and Continuous Submodular Function Minimization2020
Near-Optimal Bounds for Online Caching with Machine Learned Advice2020
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs2020
Oblivious Sketching of High-Degree Polynomial Kernels2020
Online Scheduling via Learned Weights2020
On the Learnability of Random Deep Networks2020
On the Tractability of Public Persuasion with No Externalities2020
Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis2020
Packing LPs are Hard to Solve Accurately, Assuming Linear Equations are Hard2020
Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds2020
Parallel Machine Scheduling to Minimize Energy Consumption2020
Parameterized Complexity and Approximability of Directed Odd Cycle Transversal2020
Quantifying the Burden of Exploration and the Unfairness of Free Riding2020
Reducing approximate Longest Common Subsequence to approximate Edit Distance2020
Robust Clustering Oracle and Local Reconstructor of Cluster Structure of Graphs2020
Round Complexity of Common Randomness Generation: The Amortized Setting2020
Sample Efficient Toeplitz Covariance Estimation2020
Selling Information Through Consulting2020
Small Memory Robust Simulation of Client-Server Interactive Protocols over Oblivious Noisy Channels2020
Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples2020
Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems2020
The Communication Complexity of Optimization2020
The Complexity of Contracts2020
The Directed Flat Wall Theorem2020
The Online Submodular Cover Problem2020
The Power of Distributed Verifiers in Interactive Proofs2020
The Two-Sided Game of Googol and Sample-Based Prophet Inequalities2020
Tight Bounds for the Subspace Sketch Problem with Applications2020
Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)2020
Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications2020
Ultimate greedy approximation of independent sets in subcubic graphs2020
Weighted Completion Time Minimization for Unrelated Machines via Iterative Fair Contention Resolution2020
Zeros of ferromagnetic 2-spin systems2020
(1 + ε)-Approximate Incremental Matching in Constant Deterministic Amortized Time2019
Adaptive Sparse Recovery with Limited Adaptivity2019
A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching2019
A Deterministic PTAS for the Algebraic Rank of Bounded Degree Polynomials2019
A Faster Algorithm for Minimum-Cost Bipartite Matching in Minor-Free Graphs2019
A Faster External Memory Priority Queue with DecreaseKeys2019
Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity2019
Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity.2019
Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing2019
Analysis of Ward's Method2019
A Nearly-Linear Bound for Chasing Nested Convex Bodies2019
An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation2019
A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time2019
Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness2019
Approximability of the Six-vertex Model2019

« prev Page 13/41 next »