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
Parameterized Algorithms for Survivable Network Design with Uniform Demands2018
Prophet Secretary for Combinatorial Auctions and Matroids2018
Quasi-regular sequences and optimal schedules for security games2018
Race Detection and Reachability in Nearly Series-Parallel DAGs2018
Ramsey Spanning Trees and their Applications2018
Randomized Algorithms for Online Vector Load Balancing2018
Randomized MWU for Positive LPs2018
Randomized Online Matching in Regular Graphs2018
Resource-Efficient Common Randomness and Secret-Key Schemes2018
Revenue Maximization with an Uncertainty-Averse Buyer2018
Robustly Learning a Gaussian: Getting Optimal Error, Efficiently2018
Scheduling When You Don't Know the Number of Machines2018
Separation in Correlation-Robust Monopolist Problem with Budget2018
Set Cover in Sub-linear Time2018
Space-Optimal Majority in Population Protocols2018
Stability of the Lanczos Method for Matrix Function Approximation2018
Steiner Point Removal - Distant Terminals Don't (Really) Bother2018
Steiner Point Removal with Distortion O(log k)2018
Stochastic Load Balancing on Unrelated Machines2018
Stochastic Packing Integer Programs with Few Queries2018
Sublinear Algorithms for (Δ+ 1) Vertex Coloring2018
Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems2018
Targeting and Signaling in Ad Auctions.2018
Testing bounded arboricity2018
Testing Ising Models2018
The Bane of Low-Dimensionality Clustering2018
The menu complexity of "one-and-a-half-dimensional" mechanism design2018
The Price of Information in Combinatorial Optimization2018
The Robust Sensitivity of Boolean Functions2018
The Value of Information Concealment2018
Tight Bounds on the Round Complexity of the Distributed Maximum Coverage Problem2018
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism2018
Truthful Multi-Parameter Auctions with Online Supply: an Impossible Combination2018
Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes2018
Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic Õ(n5/3) Time2018
Which Distribution Distances are Sublinearly Testable?2018
(1 + ∊)-Approximate f-Sensitive Distance Oracles2017
(1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space2017
A (2 + ∊)-Approximation for Maximum Weight Matching in the Semi-Streaming Model2017
Accurate and Nearly Optimal Sublinear Approximations to Ulam Distance2017
Adaptive Matrix Vector Product2017
Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions2017
A Hybrid Sampling Scheme for Triangle Counting2017
An FPTAS for Counting Proper Four-Colorings on Cubic Graphs2017
An Improved Upper Bound for the Universal TSP on the Grid2017
Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics2017
Approximately Sampling Elements with Fixed Rank in Graded Posets2017
Approximating Multicut and the Demand Graph2017
Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds2017
Approximation Algorithms for Label Cover and The Log-Density Threshold2017

« prev Page 17/41 next »