Machtey Award

{{primary|date=January 2020}} 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.<ref>[https://dblp.org/pid/01/3845 List of publications by Michael Machtey] at DBLP</ref> The counterpart of this award at the ACM Symposium on Theory of Computing (STOC) is the Danny Lewin Best Student Paper Award.<ref>ACM SIGACT. [http://sigact.acm.org/prizes/student/ "Danny Lewin Best Student Paper Award"] {{webarchive |url=https://web.archive.org/web/20080620010241/http://sigact.acm.org/prizes/student/ |date=June 20, 2008 }}</ref>

== Past recipients == Past recipients of the Machtey award are tabulated below.{{citation needed|date=November 2012}} {| class="wikitable" ! Year !! Recipient (University) !! Paper |- | rowspan="2" | 2025 |Miryam Mi-Ying Huang (University of Southern California) Er-Cheng Tang (University of Washington) |"Obfuscation of Unitary Quantum Programs" |- |Rahul Ilango (MIT) |"Godel in Cryptography: Effectively Zero Knowledge Proofs for NP with No Interaction, No Setup, and Perfect Soundness" |- |2024 |Brice Huang (MIT) |"Capacity Threshold for the Ising Perceptron" |- | 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"<ref>{{cite web|url=http://focs2022.eecs.berkeley.edu/awards.html|title=FOCS 2022 Best Paper Awards}}</ref> |- | 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" |- | rowspan="2" | 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" |- | rowspan="2" | 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"<ref>{{cite web|url=http://ieee-focs.org/FOCS-2017-Papers/3464z020.pdf|title=FOCS 2017 Best Paper Awards}}</ref> |- | rowspan="2" | 2016 || Michael B. Cohen (MIT) || "Ramanujan Graphs in Polynomial Time"<ref>{{cite web|url=https://www.computer.org/csdl/proceedings/focs/2016/3933/00/3933z019.pdf|title=FOCS 2016 Best Paper Awards}}</ref> |- || Aviad Rubinstein (Berkeley) || "Settling the Complexity of Computing Approximate Two-Player Nash Equilibria"<ref>{{cite web|url=https://www.computer.org/csdl/proceedings/focs/2016/3933/00/3933z019.pdf|title=FOCS 2016 Best Paper Awards}}</ref> |- | rowspan="2" | 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" <ref>{{cite web|url=http://www.eecs.berkeley.edu/focs2013/awards.html|title=FOCS 2013 Best Paper Awards|access-date=2013-12-06|archive-url=https://web.archive.org/web/20131213173034/http://www.eecs.berkeley.edu/focs2013/awards.html|archive-date=2013-12-13|url-status=dead}}</ref> |- | 2012 || Nir Bitansky (Tel Aviv University), Omer Paneth (Boston University) || "From the Impossibility of Obfuscation to a New Non-Black-Box Simulation Technique" |- | rowspan="2" | 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" |- | rowspan="2" | 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" |- | rowspan="2" | 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" |- | rowspan="2" | 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" |- | rowspan="2" | 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" |- | rowspan="2" | 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" |- | rowspan="2" | 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" |- | rowspan="2" | 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" |- | rowspan="2" | 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" |- | rowspan="2" | 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" |- | rowspan="2" | 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 (log''c'' ''n'')-wise independence in NC" |- | 1988 || Shmuel Safra (Weizmann) || "On the Complexity of omega-Automata" |- | rowspan="2" | 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" |}

==References== <references/>

Category:Awards established in 1981 Category:Computer science awards Category:IEEE awards Category:Student awards