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.

This award is named in honor of the late Daniel Lewin. The remarks made by Tom Leighton to commemorate the naming of this award can be found on this page.

Winners

2023

Guy Blanc (Stanford University) “Subsampling Suffices for Adaptive Data Analysis”.
Aleksander Bjørn Grodt Christiansen (Technical University of Denmark, DTU) “The Power of Multi-Step Vizing chains”.

2022

Rachel Yun Zhang (MIT) and Meghal Gupta (Microsoft Research) “The Optimal Error Resilience of Interactive Communication Over Binary Channels”.
Zhiyuan Fan (Tsinghua University), Jiatu Li (Tsinghua University) and Tianqi Yang (Tsinghua University) “The Exact Complexity of Pseudorandom Functions and the Black-Box Natural Proof Barrier for Bootstrapping Results in Computational Complexity”.

2021

Ryan Alweiss (Princeton University), Yang P. Liu (Stanford University), and Mehtaab Sawhney (Massachusetts Institute of Technology), “Discrepancy Minimization via a Self-Balancing Walk”.
Zachary Chase (University of Oxford), “Separating Words and Trace Reconstruction”.

2020

Siddharth Bhandari and Sayantan Chakraborty, “Improved Bounds for Perfect Sampling of $k$-colorings in Graphs”.

2019

Lijie Chen and Roei Tell, “Bootstrapping Results for Threshold Circuits ‘Just Beyond’ Known Lower Bounds”.

2018

Aaron Schild, “An Almost-Linear Time Algorithm for Uniform Random Spanning Tree Generation”.

2017

Pasin Manurangsi, “Almost-Polynomial Ratio ETH-Hardness of Approximating Densest $k$-Subgraph”.

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 Node-Connectivity 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 $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 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 $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”.