STOC Best Paper Award

The following rules for the Best Paper Award at the ACM Symposium on Theory of Computing (STOC) were developed by a committee consisting of Paul Beame, David Johnson, Prabhakar Raghavan, Eva Tardos and David Williamson (Chair). The committee developed the policy for FOCS. The same policy was adopted for STOC by the SIGACT Executive Committee, as announced in the STOC 2002 Business Meeting.

The Program Committee may designate up to three papers accepted to the conference as STOC Best Papers.
Each author on each of the selected papers will receive a certificate or plaque with the name of the award, the name of the paper, and the names of the authors of the paper, to be awarded at the Business Meeting that year.
The main criterion for selection is the same as for being a top-rated paper in the conference: introduction of a strong new technique, solution of a long-standing open problem, introduction and solution of an interesting and important new problem, etc. These are the characteristics associated with giving a paper the highest score.
Additionally, the committee should have substantial confidence in the correctness of the paper. While the committee may choose to accept papers to appear in the conference while lacking confidence that the paper is correct, such papers should not be recipients of the Best Paper Award. Since only abstracts are submitted to the conference, the committee may, after accepting a paper to the conference, inform the authors that the paper is being considered for the Award, and request additional details. It is suggested that the committee finalize its decisions on the Award in time to have the recipients listed in the proceedings of the conference. However, the committee may choose to use the time up until the conference itself to continue reviewing the papers.
The committee should verify that the final proceedings version of the paper meets the high promise of the submitted abstract.
If no paper meets the criteria above, then no award need be given.
If a paper qualifies for the Machtey/Lewin Best Student Paper Award, it should not be disqualified from being considered for the Best Paper Award, and vice versa; a paper meriting both Awards should be given both Awards.

Winners

STOC 2021

“A (Slightly) Improved Approximation Algorithm for Metric TSP”, by Anna R. Karlin (University of Washington), Nathan Klein (University of Washington), and Shayan Oveis Gharan (University of Washington).
“The Complexity of Gradient Descent: CLS = PPAD ∩ PLS”, by John Fearnley (University of Liverpool), Paul W. Goldberg (University of Oxford), Alexandros Hollender (University of Oxford), and Rahul Savani (University of Liverpool).
“Indistinguishability Obfuscation from Well-Founded Assumptions”, by Aayush Jain (University of California at Los Angeles), Huijia Lin (University of Washington), and Amit Sahai (University of California at Los Angeles).

STOC 2020

“Improved Bounds for The Sunflower Lemma”, by Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang.

STOC 2019

“Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Basis of a Matroid”, by Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant.
“The Reachability Problem for Petri Nets Is Not Elementary”, by Wojciech Czerwiński, Sławomir Lasota, Ranko Lazić, Jérôme Leroux, and Filip Mazowiecki.
“Oracle Separation of BPQ and PH”, by Ran Raz and Avishay Tal.

STOC 2018

“A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem”, by Ola Svensson, Jakub Tarnawski, and Lászaló A. Végh.

STOC 2017

“Explicit, Almost Optimal, Epsilon-Balanced Codes”, by Amnon Ta-Shma.
“Deciding Parity Games in Quasipolynomial Time”, by Cristian Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan.
“A Weighted Linear Matroid Parity Algorithm”, by Satoru Iwata and Yusuke Kobayashi.

STOC 2016

“Reed-Muller Codes Achieve Capacity on Erasure Channels”, by Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Henry D. Pfister, Eren Sasoglu, and Rudiger Urbanke.
“Explicit Two-Source Extractors and Resilient Functions”, by Eshan Chattopadhyay and David Zuckerman.
“Graph Isomorphism in Quasipolynomial Time”, by László Babai.

STOC 2015

“Exponential Separation of Information and Communication for Boolean Functions”, by Anat Ganor, Gillat Kol, and Ran Raz.
“Lower Bounds on the Size of Semidefinite Programming Relaxations”, by James Lee, Prasad Raghavendra, and David Steurer.
“ $2$ -Server PIR with Sub-Polynomial Communication”, by Zeev Dvir and Sivakanth Gopi.

STOC 2014

“The Matching Polytope Has Exponential Extension Complexity”, by Thomas Rothvoß.

STOC 2013

“Low Rank Approximation and Regression in Input Sparsity Time”, by Ken Clarkson and David Woodruff.
“Approximation Resistance from Pairwise Independent Subgroups”, by Siu On Chan.

STOC 2012

“Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds”, by Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Tiwary, and Ronald de Wolf.
“The Cell Probe Complexity of Dynamic Range Counting”, by Kasper Green Larsen.

STOC 2011

“Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs”, by Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, and Shang-Hua Teng.
“Subexponential Lower Bounds for Randomized Pivoting Rules for the Simplex Algorithm”, by Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick.

STOC 2010

“An Improved LP-Based Approximation for Steiner Tree”, by Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanità.
“QIP = PSPACE”, by Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous.

STOC 2009

“Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem”, by Chris Peikert.
“A Constructive Proof of the Lovász Local Lemma”, by Robin Moser.

STOC 2008

“Optimal Hierarchical Decompositions for Congestion Minimization in Networks”, by Harald Räcke.
“Algorithms and Inapproximability Results for Every CSP?”, by Prasad Raghavendra.

STOC 2007

“Faster Integer Multiplication”, by Martin Fürer.
“Towards $3$ -Query Locally Decodable Codes of Subexponential Length”, by Sergey Yekhanin.

STOC 2006

“The PCP Theorem via Gap Amplification”, by Irit Dinur.

STOC 2005

“Undirected ST-Connectivity in Log-Space”, by Omer Reingold.

STOC 2004

“Multi-Linear Formulas for Permanent and Determinant Are of Super-Polynomial Size”, by Ran Raz.
“Expander Flows, Geometric Embeddings and Graph Partitioning”, by Sanjeev Arora, Satish Rao, and Umesh Vazirani.

STOC 2003

“Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds”, by Valentine Kabanets and Russell Impagliazzo.
“New Lattice-Based Cryptographic Constructions”, by Oded Regev.