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
Integrality ratio for group Steiner trees and directed steiner trees2003
Lower bounds for collusion-secure fingerprinting2003
Lower bounds for embedding edit distance into normed spaces2003
Multidimensional matching and fast search in suffix trees2003
Multirate rearrangeable clos networks and a generalized edge coloring problem on bipartite graphs2003
Non-independent randomized rounding2003
Optimizing misdirection2003
Pass efficient algorithms for approximating large matrices2003
Property testing of data dimensionality2003
Random MAX SAT, random MAX CUT, and their phase transitions2003
Root comparison techniques applied to computing the additively weighted Voronoi diagram2003
Selection with monotone comparison cost2003
Smaller core-sets for balls2003
Sublinear-time approximation of Euclidean minimum spanning tree2003
The flow complex: a data structure for geometric modeling2003
Zonotopes as bounding volumes2003
A comparison of labeling schemes for ancestor queries2002
An 8/13-approximation algorithm for the asymmetric maximum TSP2002
Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems2002
Approximating k-cuts via network strength2002
Approximating minimum quartet inconsistency (abstract)2002
A randomized online algorithm for bandwidth utilization2002
Balls and bins models with feedback2002
Caching with expiration times2002
Computing the writhing number of a polygonal knot2002
Derandomized dimensionality reduction with applications2002
Efficient pattern-matching with don't cares2002
Existence theorems, lower bounds and algorithms for scheduling to meet two objectives2002
Experimental analysis of simple, distributed vertex coloring algorithms2002
Explicit constructions of selectors and related combinatorial structures, with applications2002
Frugal path mechanisms2002
Generating random factored numbers, easily2002
Guessing secrets efficiently via list decoding2002
Hardware-assisted computation of depth contours2002
How unfair is optimal routing?2002
Improved algorithms for stretch scheduling2002
Is the internet fractal?2002
Maintaining stream statistics over sliding windows (extended abstract)2002
Online algorithms for market clearing2002
On semidefinite programming relaxations for graph coloring and vertex cover2002
On the overlay of envelopes in four dimensions2002
Optimal time-space trade-offs for non-comparison-based sorting2002
Reachability and distance queries via 2-hop labels2002
Reductions in streaming algorithms, with an application to counting triangles in graphs2002
Shape dimension and approximation from samples2002
Smoothed analysis of the perceptron algorithm for linear programming2002
Static optimality and dynamic search-optimality in lists and trees2002
Symmetric drawings of triconnected planar graphs2002
Temporary tasks assignment resolved2002
Testing satisfiability2002

« prev Page 36/41 next »