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
Optimal Good-Aspect-Ratio Coarsening for Unstructured Meshes1997
Partial Matching of Planar Polylines Under Similarity Transformations1997
Rounding in Lattices and its Cryptographic Applications1997
Runtime Prediction of Real Programs on Real Machines1997
Simple Markov-Chain Algorithms for Generating Bipartite Graphs and Tournaments (Extended Abstract)1997
The Path Resistance Method for Bounding lambda2 of a Laplacian1997
An Efficient Algorithm for the Vertex-Disjoint Paths Problem in Random Graphs1996
An Extension of the Lovász Local Lemma, and its Applications to Integer Programming1996
An O(n log n) Algorithm for the Maximum Agreement Subtree Problem for Binary Trees1996
Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology1996
Efficient Generation of k-Directional Assembly Sequences1996
Fast Estimation of Diameter and Shortest Paths (without Matrix Multiplication)1996
Fully Dynamic Output Bounded Single Source Shortest Path Problem (Extended Abstract)1996
Multiprocessor Scheduling with Rejection1996
On-line Generalized Steiner Problem1996
Polynomial-Time Solutions to Image Segmentation1996
Preemptive Scheduling of Parallel Jobs on Multiprocessors1996
Randomized Robot Navigation Algorithms1996
A Fast Algorithm for the Computation and Enumeration of Perfect Phylogenies when the Number of Character States is Fixed1995
Algorithms for the Optimal Loading of Recursive Neural Nets1995
Average Case Analysis of Dynamic Graph Algorithms1995
Broadcast in Radio Networks1995
Computing the Local Consensus of Trees1995
Counting and Random Generation of Strings in Regular Languages1995
David P. Williamson: An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems1995
Fairness in Scheduling1995
Improved Algorithms for Protein Motif Recognition1995
Localizing a Robot with Minimum Travel1995
Of Mice and Men: Algorithms for Evolutionary Distances Between Genomes with Translocation1995
On the All-Pairs Euclidean Short Path Problem1995
On the Performance of Spectral Graph Partitioning Methods1995
Register Allocation in Structured Programs1995
The Statistical Adversary Allows Optimal Money-Making Trading Strategies1995
Approximate Data Structures with Applications1994
Competitive Routing of Virtual Circuits with Unknown Duration1994
Derandomizing Algorithms for Routing and Sorting on Meshes1994
Maintaining Dynamic Sequences Under Equality-Tests in Polylogarithmic Time1994
Matching Nuts and Bolts1994
Moments of Inertia and Graph Separators1994
Neighborhood Preserving Hashing and Approximate Queries1994
On Degeneracy in Geometric Computations1994
Online Interval Scheduling1994
Optimal Construction of Edge-Disjoint Paths in Random Graphs1994
Optimal Parallel Approximation for Prefix Sums and Integer Sorting1994
Scheduling Parallel Tasks to Minimize Average Response Time1994
Spanning Trees Short or Small1994
The QRQW PRAM: Accounting for Contention in Parallel Algorithms1994
Chernoff-Hoeffding Bounds for Applications with Limited Independence1993
Competitive Implementation of Parallel Programs1993
Dynamic Generation of Discrete Random Variates1993

« prev Page 40/41 next »