The following rules for Best Paper Awards 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
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
- STOC 2016: (three awards)
"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
- STOC 2015: (three awards) "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
- STOC 2014: "The Matching Polytope has Exponential Extension
Complexity", by Thomas Rothvoß.
- STOC 2013: (two awards) "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: (two awards) "Linear vs. Semidefinite
Extended Formulations: Exponential Separation and Strong Lower
Bounds", by Samuel Fiorini, Serge Massar, Sebastian Pokutta,
Hans Tiwary, Ronald de Wolf. ♦ "The Cell Probe Complexity
of Dynamic Range Counting", by Kasper Green Larsen.
- STOC 2011: (two awards) "Electrical Flows, Laplacian
Systems, and Faster Approximation of Maximum Flow in Undirected
Graphs", by Paul Christiano, Jonathan A. Kelner, Aleksander
Madry, Daniel A. Spielman, Shang-Hua Teng. ♦
"Subexponential Lower Bounds for Randomized Pivoting Rules for
the Simplex Algorithm", by Oliver Friedmann, Thomas Dueholm
Hansen, Uri Zwick.
- STOC 2010: (two awards) "An Improved LP-based
Approximation for Steiner Tree", by Jaroslaw Byrka, Fabrizio
Grandoni, Thomas Rothvoß, Laura Sanità. ♦
"QIP = PSPACE", by Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay,
- STOC 2009: (two awards) "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: (two awards) "Optimal Hierarchical
Decompositions for Congestion Minimization in Networks", by
Harald Raecke. ♦ "Algorithms and Inapproximability Results
for Every CSP?", by Prasad Raghavendra.
- STOC 2007: (two awards) "Faster Integer
Multiplication", by Martin Fürer. ♦ "Towards 3-Query
Locally Decodable Codes of Subexponential Length", by Sergey
- STOC 2006: "The PCP Theorem via Gap Amplification", by Irit
- STOC 2005: "Undirected ST-connectivity in Log-space", by
- STOC 2004: (two awards) "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, Umesh Vazirani.
- STOC 2003: (two awards) "Derandomizing Polynomial
Identity Tests Means Proving Circuit Lower Bounds", by Valentine
Kabanets, Russell Impagliazzo. ♦ "New Lattice-Based
Cryptographic Constructions", by Oded Regev.