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
editPast recipients of the Machtey award are tabulated below.[citation needed]
| Year | Recipient (University) | Paper |
|---|---|---|
| 2023 | Rahul Ilango (MIT) | "SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle" |
| 2022 | Robert Andrews (UIUC) | "On Matrix Multiplication and Polynomial Identity Testing"[3] |
| 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"[4] |
| 2016 | Michael B. Cohen (MIT) | "Ramanujan Graphs in Polynomial Time"[5] |
| Aviad Rubinstein (Berkeley) | "Settling the Complexity of Computing Approximate Two-Player Nash Equilibria"[6] | |
| 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" [7] |
| 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), |
"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" |
See also
editReferences
edit- ^ List of publications by Michael Machtey at DBLP
- ^ ACM SIGACT. "Danny Lewin Best Student Paper Award" Archived June 20, 2008, at the Wayback Machine
- ^ "FOCS 2022 Best Paper Awards".
- ^ "FOCS 2017 Best Paper Awards" (PDF).
- ^ "FOCS 2016 Best Paper Awards" (PDF).
- ^ "FOCS 2016 Best Paper Awards" (PDF).
- ^ "FOCS 2013 Best Paper Awards". Archived from the original on 2013-12-13. Retrieved 2013-12-06.