PROFILPELAJAR.COM

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

Past recipients of the Machtey award are tabulated below.^{[citation needed]}

Year	Recipient (University)	Paper
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"^[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"
2019	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"
2018	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]
2016	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"
2015	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"
2011	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"
2009	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"
2005	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"
2004	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"
2002	Harald Räcke (Paderborn)	"Minimizing Congestion in General Networks"
2001	Boaz Barak (Weizmann)	"How To Go Beyond the Black-Box Simulation Barrier"
2001	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 n²-Lower Bound for the Rank of n×n Matrix Multiplication over Arbitrary Fields"
1999	Eric Vigoda (Berkeley)	"Improved Bounds for Sampling Colorings"
1998	Kamal Jain (Georgia Tech)	"Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem"
1998	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"
1995	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"
1994	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"
1991	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"
1987	John Canny (MIT)	"A New Algebraic Method for Robot Motion Planning and Real Geometry"
1987	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"