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
Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting2016
Distance in the Forest Fire Model How far are you from Eve?2016
Evolutionary Dynamics in Finite Populations Mix Rapidly2016
Exact and Approximation Algorithms for Weighted Matroid Intersection2016
Expanders via Local Edge Flips2016
Faster Fully Dynamic Matchings with Small Approximation Ratios2016
Focused Stochastic Local Search and the Lovász Local Lemma2016
Gowers Norm, Function Limits, and Parameter Estimation2016
How to Round Subspaces: A New Spectral Clustering Algorithm2016
Improved Approximation Algorithms for k-Submodular Function Maximization2016
Improved Approximation Algorithms for-Submodular Function Maximization2016
Improved Approximation for Vector Bin Packing2016
Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile2016
Interpolating Between Truthful and non-Truthful Mechanisms for Combinatorial Auctions2016
Jointly Private Convex Programming2016
Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams2016
Learning and Efficiency in Games with Dynamic Population2016
Locality-sensitive Hashing without False Negatives2016
Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions2016
Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions.2016
Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems2016
Make-to-Order Integrated Scheduling and Distribution2016
Markovian Hitters and the Complexity of Blind Rendezvous2016
Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model2016
Multiscale Mapper: Topological Summarization via Codomain Covers2016
Natural Algorithms for Flow Problems2016
Nearly-optimal bounds for sparse recovery in generic norms, with applications to k-median sketching2016
Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform2016
Nearly Optimal NP-Hardness of Unique Coverage2016
Non-convex Compressed Sensing with the Sum-of-Squares Method2016
Online Contention Resolution Schemes2016
Online Degree-Bounded Steiner Network Design2016
Online Pricing with Impatient Bidders2016
On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion2016
On the Complexity of Dynamic Mechanism Design2016
On the Economic Efficiency of the Combinatorial Clock Auction2016
On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique2016
Packing Small Vectors2016
Partial Resampling to Approximate Covering Integer Programs2016
Persistent Homology and Nested Dissection2016
Phase Transitions in Group Testing2016
Raising The Bar For Vertex Cover: Fixed-parameter Tractability Above A Higher Guarantee2016
Recovery and Rigidity in a Regular Stochastic Block Model2016
Reducing Curse of Dimensionality: Improved PTAS for TSP (with Neighborhoods) in Doubling Metrics2016
Scheduling Parallel DAG Jobs Online to Minimize Average Flow Time2016
Scheduling Parallel DAG Jobs Online to Minimize Average Flow Time.2016
Simple and Fast Rounding Algorithms for Directed and Node-weighted Multiway Cut2016
Simple Pricing Schemes For Consumers With Evolving Values2016
Sparse Approximation via Generating Point Sets2016
Stabilizing Consensus with Many Opinions2016

« prev Page 20/41 next »