The Machtey Award
is awarded at the annual IEEE Symposium on Foundations of Computer Science

Symposium on Foundations of Computer Science

FOCS, the Annual IEEE Symposium on Foundations of Computer Science, is an academic conference in the field of theoretical computer science...

 (FOCS) to that 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. The counterpart of this award at the ACM Symposium on Theory of Computing

Symposium on Theory of Computing

STOC, the Annual ACM Symposium on Theory of Computing is an academic conference in the field of theoretical computer science. STOC has been organized annually since 1969, typically in May or June; the conference is sponsored by the Association for Computer Machinery special interest group SIGACT.As...

 (STOC) is the Danny Lewin Best Student Paper Award.

Past recipients

Year	Recipient (University)	Paper
2011	Kasper Green Larsen (Aarhus)	"On Range Searching in the Group Model and Combinatorial Discrepancy"
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 University of California, Berkeley The University of California, Berkeley , is a teaching and research university established in 1868 and located in Berkeley, California, USA... )	"Breaking the Multicommodity Flow Barrier for sqrt(log(n))-Approximations to Sparsest Cut"
2008	Mihai Pătrașcu (MIT)	"Succincter"
2007	Per Austrin (KTH Royal Institute of Technology The Royal Institute of Technology is a university in Stockholm, Sweden. KTH was founded in 1827 as Sweden's first polytechnic and is one of Scandinavia's largest institutions of higher education in technology. KTH accounts for one-third of Sweden’s technical research and engineering education... )	"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 University of Toronto The University of Toronto is a public research university in Toronto, Ontario, Canada, situated on the grounds that surround Queen's Park. It was founded by royal charter in 1827 as King's College, the first institution of higher learning in Upper Canada... )	"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 University of Warsaw The University of Warsaw is the largest university in Poland and one of the most prestigious, ranked as best Polish university in 2010 and 2011... ), Piotr Sankowski (Warsaw)	"Maximum Matchings via Gaussian Elimination"
2003	Subhash Khot (Princeton Princeton University Princeton University is a private research university located in Princeton, New Jersey, United States. The school is one of the eight universities of the Ivy League, and is one of the nine Colonial Colleges founded before the American Revolution.... )	"Hardness of Approximating the Shortest Vector Problem in High Lp Norms"
2002	Boaz Barak (Weizmann Weizmann Institute of Science The Weizmann Institute of Science , known as Machon Weizmann, is a university and research institute in Rehovot, Israel. It differs from other Israeli universities in that it offers only graduate and post-graduate studies in the sciences.... )	"Constant-Round Coin-Tossing With a Man in the Middle or Realizing Shared Random String Model"
	Harald Räcke (Paderborn University of Paderborn The University of Paderborn in Paderborn, North Rhine-Westphalia, Germany was founded in 1972. 15,228 students were enrolled at the university as of December 2010.... )	"Minimizing Congestion in General Networks"
2001	Boaz Barak (Weizmann)	"How To Go Beyond the Black-Box Simulation Barrier"
	Vladlen Koltun (Tel Aviv Tel Aviv University Tel Aviv University is a public university located in Ramat Aviv, Tel Aviv, Israel. With nearly 30,000 students, TAU is Israel's largest university.-History:... )	"Almost Tight Upper Bounds for Vertical Decompositions in Four Dimensions"
2000	Piotr Indyk Piotr Indyk Piotr Indyk is an Associate Professor in the Theory of Computation Group at the Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology.-Academic biography:...  (Stanford)	"Stable Distributions, Pseudorandom Generators, Embeddings and Data Stream Computation"
1999	Markus Bläser (Bonn University of Bonn The University of Bonn is a public research university located in Bonn, Germany. Founded in its present form in 1818, as the linear successor of earlier academic institutions, the University of Bonn is today one of the leading universities in Germany. The University of Bonn offers a large number... )	"A 5/2 n2-Lower Bound for the Rank of n×n Matrix Multiplication over Arbitrary Fields"
	Eric Vigoda (Berkeley University of California, Berkeley The University of California, Berkeley , is a teaching and research university established in 1868 and located in Berkeley, California, USA... )	"Improved Bounds for Sampling Colorings"
1998	Kamal Jain (Georgia Tech Georgia Institute of Technology The Georgia Institute of Technology is a public research university in Atlanta, Georgia, in the United States... )	"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 Carnegie Mellon University Carnegie Mellon University is a private research university in Pittsburgh, Pennsylvania, United States.... )	"A Random Sampling Based Algorithm for Learning the Intersection of Half-spaces"
1996	Jon Kleinberg Jon Kleinberg -External links:**** Stephen Ibaraki*Yury Lifshits,...  (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 University of Chicago The University of Chicago is a private research university in Chicago, Illinois, USA. It was founded by the American Baptist Education Society with a donation from oil magnate and philanthropist John D. Rockefeller and incorporated in 1890... )	"Spectral Methods for Matrix Rigidity with Applications to Size-Depth Tradeoffs and Communication Complexity"
1994	Rakesh K. Sinha, T.S. Jayram (Washington University of Washington University of Washington is a public research university, founded in 1861 in Seattle, Washington, United States. The UW is the largest university in the Northwest and the oldest public university on the West Coast. The university has three campuses, with its largest campus in the University... )	"Efficient Oblivious Branching Programs for Threshold Functions"
1993	?
1992	Bernd Gärtner (FU Berlin Free University of Berlin Freie Universität Berlin is one of the leading and most prestigious research universities in Germany and continental Europe. It distinguishes itself through its modern and international character. It is the largest of the four universities in Berlin. Research at the university is focused on the... )	"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	?
1988	Shmuel Safra Shmuel Safra Shmuel Safra is a Professor of Computer Science at Tel Aviv University, Israel. Born in Jerusalem.Safra's research areas include Complexity Theory and Automata Theory...  (Weizmann)	"On the Complexity of omega-Automata"
1987	John Canny John Canny John F. Canny is an Australian computer scientist, and Paul and Stacy Jacobs Distinguished Professor of Engineering in the Computer Science Department of the University of California, Berkeley...  (MIT)	"A New Algebraic Method for Robot Motion Planning and Real Geometry"
	Abhiram G. Ranade (Yale YALE RapidMiner, formerly YALE , is an environment for machine learning, data mining, text mining, predictive analytics, and business analytics. It is used for research, education, training, rapid prototyping, application development, and industrial applications... )	"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 Harry Mairson Harry George Mairson is a theoretical computer scientist and Professor of Computer Science in the at Brandeis University in Waltham, Massachusetts. His research is in the fields of logic in computer science, lambda calculus and functional programming, type theory and constructive mathematics,...  (Stanford)	"The Program Complexity of Searching a Table"
1982	Carl Sturtivant	"Generalized Symmetries of Polynomials in Algebraic Complexity"
1981	F. Thomson Leighton F. Thomson Leighton Frank Thomson "Tom" Leighton is a professor of Applied Mathematics at the Massachusetts Institute of Technology. He has served as the head of the Algorithms group at MIT's Computer Science and Artificial Intelligence Laboratory since 1996, and co-founded Akamai Technologies with student Daniel... (MIT)	"New Lower Bound Techniques for VLSI"