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
Testing Planarity of Partially Embedded Graphs2010
The (1 + beta)-Choice Process and Weighted Balls-into-Bins2010
The Edge Disjoint Paths Problem in Eulerian Graphs and 4-edge-connected Graphs2010
The Rank of Diluted Random Graphs2010
Thin Partitions: Isoperimetric Inequalities and a Sampling Algorithm for Star Shaped Bodies2010
Towards the Randomized k-Server Conjecture: A Primal-Dual Approach2010
Tree Embeddings for Two-Edge-Connected Network Design2010
Utilitarian Mechanism Design for Multi-Objective Optimization2010
Additive approximation algorithms for list-coloring minor-closed class of graphs2009
Algorithms for finding an induced cycle in planar graphs and bounded genus graphs2009
Analysis of scalar fields over point cloud data2009
A near-linear time algorithm for constructing a cactus representation of minimum cuts2009
A nearly linear time algorithm for the half integral parity disjoint paths packing problem2009
An improved approximation algorithm for the column subset selection problem2009
Approximate clustering without the approximation2009
Approximate Euclidean shortest paths amid convex obstacles2009
Approximate line nearest neighbor in high dimensions2009
Approximating submodular functions everywhere2009
A simpler implementation and analysis of Chazelle's soft heaps2009
Assignment problem in content distribution networks: unsplittable hard-capacitated facility location2009
Better algorithms for benign bandits2009
Collecting weighted items from a dynamic queue2009
Combinatorial algorithms for nearest neighbors, near-duplicates and small-world design2009
Combinatorial algorithms for wireless information flow2009
Combinatorial stochastic processes and nonparametric Bayesian modeling2009
Compressed counting2009
Computing the nucleolus of weighted voting games2009
Constructing Laplace operator from point clouds in2009
Constructing Laplace operator from point clouds in R.d2009
Constructing Laplace operator from point clouds in Rd2009
Efficient coordination mechanisms for unrelated machine scheduling2009
Exact algorithms for partial curve matching via the Fréchet distance2009
Expanders via random spanning trees2009
Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures2009
Finding duplicates in a data stream2009
Generating random graphs with large girth2009
How hard is it to approximate the best Nash equilibrium?2009
Improved approximating algorithms for Directed Steiner Forest2009
Improved approximation bound for quadratic optimization problems with orthogonality constraints2009
Improved equilibria via public service advertising2009
Improved smoothed analysis of the k-means method2009
Line transversals of convex polyhedra in R32009
List-color-critical graphs on a fixed surface2009
Monotone minimal perfect hashing: searching a sorted table with O(1) accesses2009
Multi-dimensional online tracking2009
Online scheduling to minimize the maximum delay factor2009
Online scheduling to minimize the maximum delay factor.2009
Online story scheduling in web advertising2009
On the approximability of Dodgson and Young elections2009
On the complexity of Nash equilibria of action-graph games2009

« prev Page 29/41 next »