Machtey Award


The Machtey Award is awarded at the annual IEEE Symposium on Foundations of Computer Science to the author of the best student paper. 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. The counterpart of this award at the ACM Symposium on Theory of Computing is the Danny Lewin Best Student Paper Award.

Past recipients

Past recipients of the Machtey award are tabulated below.
YearRecipient Paper
2019Jason Li "Faster Minimum k-cut of a Simple Graph."
Josh Alman
Lijie Chen
"Efficient Construction of Rigid Matrices Using an NP Oracle"
2018Shuichi Hirahara "Non-black-box Worst-case to Average-case Reductions within NP"
Urmila Mahadev "Classical Verification of Quantum Computation"
2017Rasmus Kyng
Peng Zhang
"Hardness Results for Structured Linear Systems"
2016Michael B. Cohen "Ramanujan Graphs in Polynomial Time"
Aviad Rubinstein "Settling the Complexity of Computing Approximate Two-Player Nash Equilibria"
2015Mika Göös "Lower Bounds for Clique vs. Independent Set"
Aaron Sidford
Yin Tat Lee
Sam Chiu-wai Wong
"A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization"
2014Aaron Sidford
Yin Tat Lee
"Path-Finding Methods for Linear Programming : Solving Linear Programs in Õ Iterations and Faster Algorithms for Maximum Flow"
2013Jonah Sherman "Nearly Maximum Flows in Nearly Linear Time"
2012Nir Bitansky,
Omer Paneth
"From the Impossibility of Obfuscation to a New Non-Black-Box Simulation Technique"
2011Kasper Green Larsen "On Range Searching in the Group Model and Combinatorial Discrepancy"
Timon Hertli "3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General"
2010Aaron Potechin "Bounds on Monotone Switching Networks for Directed Connectivity"
2009Alexander Sherstov "The intersection of two halfspaces has high threshold degree"
Jonah Sherman "Breaking the Multicommodity Flow Barrier for sqrt-Approximations to Sparsest Cut"
2008Mihai Pătraşcu "Succincter"
2007Per Austrin "Towards sharp inapproximability for any 2-CSP"
2006Nicholas J. A. Harvey "Algebraic Structures and Algorithms for Matching and Matroid Problems"
2005Mark Braverman "On the Complexity of Real Functions"
Tim Abbott,

Daniel Kane,

Paul Valiant
"On the Complexity of Two-Player Win-Lose Games"
2004Lap Chi Lau "An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem"
Marcin Mucha,

Piotr Sankowski
"Maximum Matchings via Gaussian Elimination"
2003Subhash Khot "Hardness of Approximating the Shortest Vector Problem in High Lp Norms"
2002Boaz Barak "Constant-Round Coin-Tossing With a Man in the Middle or Realizing Shared Random String Model"
Harald Räcke "Minimizing Congestion in General Networks"
2001Boaz Barak "How To Go Beyond the Black-Box Simulation Barrier"
Vladlen Koltun "Almost Tight Upper Bounds for Vertical Decompositions in Four Dimensions"
2000Piotr Indyk "Stable Distributions, Pseudorandom Generators, Embeddings and Data Stream Computation"
1999Markus Bläser "A 5/2 n2-Lower Bound for the Rank of n×n Matrix Multiplication over Arbitrary Fields"
Eric Vigoda "Improved Bounds for Sampling Colorings"
1998Kamal Jain "Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem"
Daniele Micciancio "The shortest vector problem is NP-hard to approximate to within some constant"
1997Santosh Vempala "A Random Sampling Based Algorithm for Learning the Intersection of Half-spaces"
1996Jon Kleinberg "Single-Source Unsplittable Flow"
1995Andras Benczur "A Representation of Cuts within 6/5 Times the Edge Connectivity with Applications"
Satyanarayana V. Lokam "Spectral Methods for Matrix Rigidity with Applications to Size-Depth Tradeoffs and Communication Complexity"
1994Rakesh K. Sinha,

T.S. Jayram
"Efficient Oblivious Branching Programs for Threshold Functions"
Jeffrey C. Jackson "An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform Distribution"
1993Pascal Koiran"A Weak Version of the Blum, Shub & Smale model"
1992Bernd Gärtner "A Subexponential Algorithm for Abstract Optimization Problems"
1991Anna Gal "Lower bounds for the complexity of reliable Boolean circuits with noisy gates"
Jaikumar Radhakrishnan "Better Bounds for Threshold Formulas"
1990David Zuckerman "General weak random sources"
1989Bonnie Berger
John Rompel
"Simulating -wise independence in NC"
1988Shmuel Safra "On the Complexity of omega-Automata"
1987John Canny "A New Algebraic Method for Robot Motion Planning and Real Geometry"
Abhiram G. Ranade "How to Emulate Shared Memory "
1986Prabhakar Raghavan "Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs"
1985Ravi B. Boppana "Amplification of Probabilistic Boolean Formulas"
1984Joel Friedman "Constructing O Size Monotone Formulae for the k-th Elementary Symmetric Polynomial of n Boolean Variables"
1983Harry Mairson "The Program Complexity of Searching a Table"
1982Carl Sturtivant "Generalized Symmetries of Polynomials in Algebraic Complexity"
1981F. Thomson Leighton "New Lower Bound Techniques for VLSI"