# 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”.