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
Best-Response Dynamics in Combinatorial Auctions with Item Bidding.2017
Better Approximations for Tree Sparsity in Nearly-Linear Time2017
Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs2017
Bridging the Capacity Gap Between Interactive and One-Way Communication2017
Building a Good Team: Secretary Problems and the Supermodular Degree2017
Combinatorial Prophet Inequalities2017
Competitive analysis of the top-K ranking problem2017
Computing minimum cuts in hypergraphs2017
Computing Walrasian Equilibria: Fast Algorithms and Structural Properties2017
Constant Approximation Algorithm for Non-Uniform Capacitated Multi-Item Lot-Sizing via Strong Covering Inequalities2017
Counting matchings in irregular bipartite graphs and random lifts2017
Cross-Referenced Dictionaries and the Limits of Write Optimization2017
Distance Sensitive Bloom Filters Without False Negatives2017
Doubly Balanced Connected Graph Partitioning2017
Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications2017
ETH Hardness for Densest-k-Subgraph with Perfect Completeness2017
Explicit Resilient Functions Matching Ajtai-Linial2017
Exponential Segregation in a Two-Dimensional Schelling Model with Tolerant Individuals2017
Fair Coin Flipping: Tighter Analysis and the Many-Party Case2017
Fair Scheduling via Iterative Quasi-Uniform Sampling2017
Fair Scheduling via Iterative Quasi-Uniform Sampling.2017
Faster Algorithms for Computing Maximal 2-Connected Subgraphs in Sparse Directed Graphs2017
Faster Online Matrix-Vector Multiplication2017
Faster Sublinear Algorithms using Conditional Sampling2017
Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion2017
Find Your Place: Simple Distributed Algorithms for Community Detection2017
Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log3 n) Worst Case Update Time2017
High-dimensional approximate r-nets2017
Input Sparsity Time Low-rank Approximation via Ridge Leverage Score Sampling2017
LAST but not Least: Online Spanners for Buy-at-Bulk2017
Linear Diophantine Equations, Group CSPs, and Graph Isomorphism2017
Local Flow Partitioning for Faster Edge Connectivity2017
Locally Testable and Locally Correctable Codes Approaching the Gilbert-Varshamov Bound2017
Low-Rank PSD Approximation in Input-Sparsity Time2017
LP-Based Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs2017
LP Relaxations of Some NP-Hard Problems Are as Hard as Any LP2017
LSH Forest: Practical Algorithms Made Theoretical2017
Make Up Your Mind: The Price of Online Queries in Differential Privacy2017
Massively-Parallel Similarity Join, Edge-Isoperimetry, and Distance Correlations on the Hypercube2017
Maximally Recoverable Codes for Grid-like Topologies2017
MDS Code Constructions with Small Sub-packetization and Near-optimal Repair Bandwidth2017
Metric embeddings with outliers2017
Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits2017
Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion2017
Near-Linear Time Approximation Schemes for some Implicit Fractional Packing Problems2017
Near-Optimal (Euclidean) Metric Compression2017
Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Õ (log) Time (Extended Abstract)2017
Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Õ (m10/7 log W) Time (Extended Abstract)2017
O(depth)-Competitive Algorithm for Online Multi-level Aggregation2017
On Estimating Maximum Matching Size in Graph Streams2017

« prev Page 18/41 next »