
The Association for Computing Machinery 

SIGACT
awards a
prize
for the best student paper each year at the
ACM Symposium on
Theory of Computing, as judged by the Program Committee.
A prize of $500 will be given to the author(s) of the best
studentauthored paper (or split between more than one
paper if there is a tie).
A paper is eligible if all of its authors are fulltime students
at the time of submission.
This must be indicated in the submission cover letter or
(for electronic submissions) the registration process.
Remarks made by Tom
Leighton to commemorate the naming of the STOC Best Student Paper Award in honor
of the late Daniel Lewin.
Past Winners
 2017: Pasin Manurangsi, "AlmostPolynomial Ratio ETHHardness of Approximating Densest KSubgraph"
 2016: Leqi Zhu, "A Tight Space Bound for Consensus"; Amir Abboud and Greg Bodwin, "The 4/3 Additive Spanner Exponent is Tight"
 2015: Aviad Rubinstein, "Inapproximability of Nash Equilibrium"
 2014: Paul F. Christiano, "Online Learning of Local Structure via
Semidefinite Programming"
 2013: Aaron Bernstein, "Maintaining Shortest Paths Under
Deletions in Weighted Directed Graphs";
Siu On Chan, "Approximation Resistance from Pairwise Independent
Subgroups"
 2012: Kasper Green Larsen,
"The Cell Probe Complexity of Dynamic Range Counting"
 2011: Bernhard Haeupler,
"Analyzing Network Coding Gossip Made Easy"
 2010: László Végh,
"Augmenting Undirected NodeConnectivity by One"
 2009: Robin Moser,
"A constructive proof of the Lovász Local Lemma"
 2008: Prasad Raghavendra,
"Algorithms and Inapproximability Results for Every CSP?"
 2007: Sergey Yekhanin,
"Towards 3Query Locally Decodable Codes of Subexponential Length"
 2006: Jakob Nordstrom,
"Narrow Proofs May Be Spacious: Separating Space and Width in Resolution";
Anup Rao,
"Extractors for a Constant Number of Polynomial MinEntropy Independent Sources"
 2005: Vladimir Trifonov,
"A O(log n log log n) Space Algorithm for Undirected Connectivity"
 2004: Scott Aaronson,
"Lower Bounds for Local Search by Quantum Arguments";
Jonathan Kelner,
"Spectral Partitioning, Eigenvalue Bounds, and Circle Packings for Graphs of Bounded Genus"
 2003: Thomas P. Hayes,
"Randomly Coloring Graphs of Girth At Least Five"
 2002:
Tim Roughgarden, "The Price of Anarchy is Independent of the Network Topology"
 2001:
Adam Klivans and Rocco Servedio, "Learning DNF in Time 2^{O(n^{1/3})}"
 2000: Andris Ambainis,
"Quantum Lower Bounds by Quantum Arguments"
 1999: Moses Charikar and Sudipto Guha,
"A Constant Factor Approximation for the kMedian Problem"
 1998:
(no award given)
 1997: Luca Trevisan,
"When Hamming Meets Euclid: The Approximability of Geometric TSP and MST"
 1996: Amnon TaShma,
"On Extracting Randomness from Weak Random Sources"
 1995: Daniel A. Spielman,
"LinearTime Encodable and Decodable ErrorCorrecting Codes"
 1994: Ramesh Harihan,
"Optimal Parallel Suffix Tree Construction";
Alexander Polishchuk and Daniel A. Spielman,
"Nearlylinear Size Holographic Proofs"
 1993: M. Kharitonov,
"Cryptographic Hardness of Distribution Specific Learning"
 1992: P. Kelson,
"On Computing a Maximal Independent Set in a Hypergraph of Constant Dimension in Parallel";
A. Panconesi and A. Srinivasan,
"Improved Algorithms for Coloring and Network Decomposition Problems"
 1991:
(no award given)
 1990: J. A. La Poutré,
"Lower Bounds for the UnionFind and SplitFind Problem on Pointer Machines";
John Rompel,
"OneWay Functions are Necessary and Sufficient for Digital Signatures"
 1989: Tomás Feder,
"A New Fixed Point Approach for Stable Networks and Stable Marriages"
Latest update:
20170615
