Danny Lewin Best Student Paper Award

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 student-authored paper (or split between more than one paper if there is a tie). A paper is eligible if all of its authors are full-time 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

2007: Sergey Yekhanin, "Towards 3-Query 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 Min-Entropy 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 Rocc 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 k-Median Problem"
1998: no award given
1997: Luca Trevisan, "When Hamming Meets Euclid: The Approximability of Geometric TSP and MST"
1996: Amnon Ta-Shma, "On Extracting Randomness from Weak Random Sources"
1995: Daniel A. Spielman, "Linear-Time Encodable and Decodable Error-Correcting Codes"
1994: Ramesh Harihan, "Optimal Parallel Suffix Tree Construction"; Alexander Polishchuk and Daniel A. Spielman, "Nearly-linear 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 Union-Find and Split-Find Problem on Pointer Machines"; John Rompel, "One-Way Functions are Necessary and Sufficient for Digital Signatures"
1989: Tomás Feder, "A New Fixed Point Approach for Stable Networks and Stable Marriages"

Created by Ian Parberry, March 31, 1999.
Last updated Wed Nov 8 17:50:18 CST 2000