The Machtey Award is awarded at the annual IEEE Symposium on Foundations of Computer Science (FOCS) to the author(s) of the best student paper(s). A paper qualifies as a student paper if all authors are full-time students at the date of the submission. The award decision is made by the Program Committee.
The award is named after Michael Machtey, who was a researcher in the theoretical computer science community in the 1970s.[1] The counterpart of this award at the ACM Symposium on Theory of Computing (STOC) is the Danny Lewin Best Student Paper Award.[2]
Past recipients of the Machtey award are tabulated below.
| Year | Recipient (University) | Paper | |
|---|---|---|---|
| 2021 | Xiao Mao (MIT) | "Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance" | |
| 2020 | Rahul Ilango (MIT) | "The Constant Depth Formula and Partial Function Versions of MCSP are Hard" | |
| 2019 | Jason Li (CMU) | "Faster Minimum k-cut of a Simple Graph" | |
| Josh Alman (MIT) Lijie Chen (MIT) | "Efficient Construction of Rigid Matrices Using an NP Oracle" | ||
| 2018 | Shuichi Hirahara (The University of Tokyo) | "Non-black-box Worst-case to Average-case Reductions within NP" | |
| Urmila Mahadev (UC Berkeley) | "Classical Verification of Quantum Computation" | ||
| 2017 | Rasmus Kyng (Yale) Peng Zhang (Georgia Tech) | "Hardness Results for Structured Linear Systems"[3] | |
| 2016 | Michael B. Cohen (MIT) | "Ramanujan Graphs in Polynomial Time"[4] | |
| Aviad Rubinstein (Berkeley) | "Settling the Complexity of Computing Approximate Two-Player Nash Equilibria"[5] | ||
| 2015 | Mika Göös (University of Toronto) | "Lower Bounds for Clique vs. Independent Set" | |
| Aaron Sidford (MIT) Yin Tat Lee (MIT) Sam Chiu-wai Wong (University of California, Berkeley) | "A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization" | ||
| 2014 | Aaron Sidford (MIT) Yin Tat Lee (MIT) | "Path-Finding Methods for Linear Programming : Solving Linear Programs in Õ(√rank) Iterations and Faster Algorithms for Maximum Flow" | |
| 2013 | Jonah Sherman (University of California, Berkeley) | "Nearly Maximum Flows in Nearly Linear Time" [6] | |
| 2012 | Nir Bitansky (Tel Aviv University), Omer Paneth (Boston University) | "From the Impossibility of Obfuscation to a New Non-Black-Box Simulation Technique" | |
| 2011 | Kasper Green Larsen (Aarhus) | "On Range Searching in the Group Model and Combinatorial Discrepancy" | |
| Timon Hertli (ETH Zurich) | "3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General" | ||
| 2010 | Aaron Potechin (MIT) | "Bounds on Monotone Switching Networks for Directed Connectivity" | |
| 2009 | Alexander Sherstov (UT Austin) | "The intersection of two halfspaces has high threshold degree" | |
| Jonah Sherman (University of California, Berkeley) | "Breaking the Multicommodity Flow Barrier for sqrt(log(n))-Approximations to Sparsest Cut" | ||
| 2008 | Mihai Pătraşcu (MIT) | "Succincter" | |
| 2007 | Per Austrin (KTH) | "Towards sharp inapproximability for any 2-CSP" | |
| 2006 | Nicholas J. A. Harvey (MIT) | "Algebraic Structures and Algorithms for Matching and Matroid Problems" | |
| 2005 | Mark Braverman (Toronto) | "On the Complexity of Real Functions" | |
| Tim Abbott (MIT), Daniel Kane (MIT), Paul Valiant (MIT) | "On the Complexity of Two-Player Win-Lose Games" | ||
| 2004 | Lap Chi Lau (Toronto) | "An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem" | |
| Marcin Mucha (Warsaw), Piotr Sankowski (Warsaw) | "Maximum Matchings via Gaussian Elimination" | ||
| 2003 | Subhash Khot (Princeton) | "Hardness of Approximating the Shortest Vector Problem in High Lp Norms" | |
| 2002 | Boaz Barak (Weizmann) | "Constant-Round Coin-Tossing With a Man in the Middle or Realizing Shared Random String Model" | |
| Harald Räcke (Paderborn) | "Minimizing Congestion in General Networks" | ||
| 2001 | Boaz Barak (Weizmann) | "How To Go Beyond the Black-Box Simulation Barrier" | |
| Vladlen Koltun (Tel Aviv) | "Almost Tight Upper Bounds for Vertical Decompositions in Four Dimensions" | ||
| 2000 | Piotr Indyk (Stanford) | "Stable Distributions, Pseudorandom Generators, Embeddings and Data Stream Computation" | |
| 1999 | Markus Bläser (Bonn) | "A 5/2 n2-Lower Bound for the Rank of n×n Matrix Multiplication over Arbitrary Fields" | |
| Eric Vigoda (Berkeley) | "Improved Bounds for Sampling Colorings" | ||
| 1998 | Kamal Jain (Georgia Tech) | "Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem" | |
| Daniele Micciancio (MIT) | "The shortest vector problem is NP-hard to approximate to within some constant" | ||
| 1997 | Santosh Vempala (CMU) | "A Random Sampling Based Algorithm for Learning the Intersection of Half-spaces" | |
| 1996 | Jon Kleinberg (MIT) | "Single-Source Unsplittable Flow" | |
| 1995 | Andras Benczur (MIT) | "A Representation of Cuts within 6/5 Times the Edge Connectivity with Applications" | |
| Satyanarayana V. Lokam (Chicago) | "Spectral Methods for Matrix Rigidity with Applications to Size-Depth Tradeoffs and Communication Complexity" | ||
| 1994 | Rakesh K. Sinha, T.S. Jayram (Washington) | "Efficient Oblivious Branching Programs for Threshold Functions" | |
| Jeffrey C. Jackson (CMU) | "An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform Distribution" | ||
| 1993 | Pascal Koiran | "A Weak Version of the Blum, Shub & Smale model" | |
| 1992 | Bernd Gärtner (FU Berlin) | "A Subexponential Algorithm for Abstract Optimization Problems" | |
| 1991 | Anna Gal (Chicago) | "Lower bounds for the complexity of reliable Boolean circuits with noisy gates" | |
| Jaikumar Radhakrishnan (Rutgers) | "Better Bounds for Threshold Formulas" | ||
| 1990 | David Zuckerman (Berkeley) | "General weak random sources" | |
| 1989 | Bonnie Berger (MIT) John Rompel (MIT) | "Simulating (logc n)-wise independence in NC" | |
| 1988 | Shmuel Safra (Weizmann) | "On the Complexity of omega-Automata" | |
| 1987 | John Canny (MIT) | "A New Algebraic Method for Robot Motion Planning and Real Geometry" | |
| Abhiram G. Ranade (Yale) | "How to Emulate Shared Memory (Preliminary Version)" | ||
| 1986 | Prabhakar Raghavan (Berkeley) | "Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs" | |
| 1985 | Ravi B. Boppana (MIT) | "Amplification of Probabilistic Boolean Formulas" | |
| 1984 | Joel Friedman (Harvard) | "Constructing O(n log n) Size Monotone Formulae for the k-th Elementary Symmetric Polynomial of n Boolean Variables" | |
| 1983 | Harry Mairson (Stanford) | "The Program Complexity of Searching a Table" | |
| 1982 | Carl Sturtivant (University of Minnesota) | "Generalized Symmetries of Polynomials in Algebraic Complexity" | |
| 1981 | F. Thomson Leighton (MIT) | "New Lower Bound Techniques for VLSI" |