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
On the Optimality of Parsing in Dynamic Dictionary Based Data Compression1999
Optimal Multichannel Communication Under Failure1999
Optimal Scheduling of Multiclass Parallel Machines1999
Packet Filtering in High Speed Networks1999
Page Replacement for General Caching Problems1999
Roundness Estimation via Random Sampling1999
Scheduling Calls for Multicasting in Tree-Networks1999
Scheduling Multicasts on Unit-Capacity Trees and Meshes1999
Separation-Sensitive Collision Detection for Convex Objects1999
Synopsis Data Structures for Massive Data Sets1999
The Full Degree Spanning Tree Problem1999
Tree Pattern Matching and Subset Matching in Deterministic(log)-time1999
Tree Pattern Matching and Subset Matching in Deterministic O(n log3 n)-time1999
Unscrambling Address Lines1999
Wavelength Conversion in Optical Networks1999
What are the Least Tractable Instances of max Independent Set?1999
Analysis of Random Processes via And-Or Tree Evaluation1998
Ancient and New Algorithms for Load Balancing in the Lp Norm1998
A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem1998
A Polynomial Time Approximation Scheme for Minimum Routing Cost Spanning Trees1998
A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP1998
Approximate String Matching: A Simpler Faster Algorithm1998
Approximation Algorithms for Directed Steiner Problems1998
Average-Case Analyses of First Fit and Random Fit Bin Packing1998
Computation in Noisy Radio Networks1998
Fast Distributed Algorithms for {Brooks-Vizing} Colourings1998
Flow and Stretch Metrics for Scheduling Continuous Job Streams1998
Kinetic Binary Space Partitions for Intersecting Segments and Disjoint Triangles (Extended Abstract)1998
Learning Deterministic Finite Automata from Smallest Counterexamples1998
On-line Randomized Call Control Revisited1998
Online Throughput-Competitive Algorithm for Multicast Routing and Admission Control1998
On the Distributed Complexity of Computing Maximal Matchings1998
Theory and Practice of I/O-Efficient Algorithms for Multidimensional Batched Searching Problems (Extended Abstract)1998
All-Pairs Small-Stretch Paths1997
An Efficient Algorithm for Terraine Simplification1997
Approximating Matrix Multiplication for Pattern Recognition Tasks1997
Approximation Schemes for Scheduling1997
Approximation Techniques for Average Completion Time Scheduling1997
A Strong and Easily Computable Separation Bound for Arithmetic Expressions Involving Square Roots1997
Better Approximation Guarantees for Job-shop Scheduling1997
Buy-at-Bulk Network Design: Approximating the Single-Sink Edge Installation Problem1997
Combinatorial Optimization Games1997
Data Structures for Mobile Data1997
Experimental Study of Minimum Cut Algorithms1997
Improving the Discrepancy Bound for Sparse Matrices: Better Approximations for Sparse Lattice Approximation Problems1997
Information Retrieval Algorithms: A Survey1997
Map Labeling and Its Generalizations1997
Nearly Optimal Distributed Edge Colouring in O(log log n) Rounds1997
Online List Accessing Algorithms and Their Applications: Recent Empirical Evidence1997
On Page Migration and Other Relaxed Task Systems1997

« prev Page 39/41 next »