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
Beyond Locality-Sensitive Hashing2014
Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut2014
Broadcast Throughput in Radio Networks: Routing vs. Network Coding2014
Cache-Adaptive Algorithms2014
Causal Erasure Channels2014
Competitive Analysis via Regularization2014
Concurrent Range Reporting in Two-Dimensional Space2014
Constrained Signaling in Auction Design2014
Cutting corners cheaply, or how to remove Steiner points2014
Dantzig's pivoting rule for shortest paths, deterministic MDPs, and minimum cost to time ratio cycles2014
Dynamic Task Allocation in Asynchronous Shared Memory2014
Efficient quantum protocols for XOR functions2014
Exploiting Metric Structure for Efficient Private Query Release2014
Fast Computation of Output-Sensitive Maxima in a Word RAM2014
Flow-Based Algorithms for Local Graph Clustering2014
Hallucination Helps: Energy Efficient Virtual Circuit Routing2014
Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs2014
Hypercontractive inequalities via SOS, and the Frankl-Rödl graph2014
Improved Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs2014
Improved Approximation Algorithm for Two-Dimensional Bin Packing2014
Improved bounds and algorithms for graph cuts and network reliability2014
Improved Concentration Bounds for Count-Sketch2014
Improvements and Generalizations of Stochastic Knapsack and Multi-Armed Bandit Approximation Algorithms: Extended Abstract2014
Influence Maximization in Undirected Networks2014
Integer quadratic programming in the plane2014
Learning Entangled Single-Sample Gaussians2014
Learning Sparse Polynomial Functions2014
Linear-Time FPT Algorithms via Network Flow2014
Maintaining Assignments Online: Matching, Scheduling, and Flows2014
Maximizing Social Influence in Nearly Optimal Time2014
Minimum Common String Partition Parameterized by Partition Size Is Fixed-Parameter Tractable2014
Minimum d-dimensional arrangement with fixed points2014
Model-based Sketching and Recovery with Expanders2014
(Nearly) Sample-Optimal Sparse Fourier Transform2014
Near-optimal labeling schemes for nearest common ancestors2014
New Approximations for Reordering Buffer Management2014
New constructions of RIP matrices with fast multiplication and fewer rows2014
Non-Uniform Graph Partitioning2014
Online Steiner Tree with Deletions2014
On Sketching Matrix Norms and the Top Singular Vector2014
On the compatibility of quartet trees2014
Optimal Algorithms for Testing Closeness of Discrete Distributions2014
Optimal Deterministic Shallow Cuttings for 3D Dominance Ranges2014
Optimization Despite Chaos: Convex Relaxations to Complex Limit Sets via Poincaré Recurrence2014
Pipage Rounding, Pessimistic Estimators and Matrix Concentration2014
Prophet Inequalities with Limited Information2014
Ranking on Arbitrary Graphs: Rematch via Continuous LP with Monotone and Boundary Condition Constraints2014
Relative Errors for Deterministic Low-Rank Matrix Approximations2014
Smoothed Analysis of Local Search for the Maximum-Cut Problem2014
Solving 1-Laplacians in Nearly Linear Time: Collapsing and Expanding a Topological Ball2014

« prev Page 23/41 next »