FOCS Best Student Paper Award (Machtey Award)

The Machtey Award is the name of the award presented to the best student paper(s) at the IEEE Symposium on Foundations of Computer Science (FOCS). It is named after Michael Machtey, who was a researcher in the theoretical computer science community in the 1970's. The counterpart of this award at the ACM Symposium on Theory of Computation is the STOC Best Student Paper Award (Danny Lewin Award).

Recipients of the Machtey Award

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"
Andrei A. Bulatov (Oxford), "A Dichotomy Theorem for Constraints on a Three-Element Set"
Harald Raecke (Universitat 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 Blaser (Universitat Bonn), "A 5/2n^2-Lower Bound for the Rank of n x n-Matrix Multiplication over Arbitrary Fields"
Eric Vigoda (UC 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 (Washington), Jayram S. Thathachar (Washington), "Efficient Oblivious Branching Programs for Threshold Functions"

1993

?

1992

Bernd Gartner (Freie Universitat 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 (UC Berkeley), "General weak random sources"

1989

?

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 (UC 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 G. Mairson (Stanford), "The Program Complexity of Searching a Table"

1982

?

1981

F. Thomson Leighton (MIT), "New Lower Bound Techniques for VLSI"