The Machtey Award is awarded at the annual IEEE

Symposium on Foundations of Computer Science The IEEE Annual Symposium on Foundations of Computer Science (FOCS) is an academic conference in the field of theoretical computer science. FOCS is sponsored by the IEEE Computer Society. As writes, FOCS and its annual Association for Computing ...

(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. The counterpart of this award at the ACM

Symposium on Theory of Computing The Annual ACM Symposium on Theory of Computing (STOC) 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 ...

(STOC) is the

Danny Lewin Best Student Paper Award The Annual ACM Symposium on Theory of Computing (STOC) 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 ...

Past recipients

Past recipients of the Machtey award are tabulated below. {, class="wikitable" ! Year !! Recipient (University) !! Paper , - , 2024 , Brice Huang (

MIT The Massachusetts Institute of Technology (MIT) is a private research university in Cambridge, Massachusetts, United States. Established in 1861, MIT has played a significant role in the development of many areas of modern technology and sc ...

) , "Capacity Threshold for the Ising Perceptron" , - , 2023 , , Rahul Ilango (

) , , "SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle" , - , 2022 , , Robert Andrews (

UIUC The University of Illinois Urbana-Champaign (UIUC, U of I, Illinois, or University of Illinois) is a public land-grant research university in the Champaign–Urbana metropolitan area, Illinois, United States. Established in 1867, it is the f ...

) , , "On Matrix Multiplication and Polynomial Identity Testing" , - , 2021 , , Xiao Mao (

) , , "Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance" , - , 2020 , , Rahul Ilango (

) , , "The Constant Depth Formula and Partial Function Versions of MCSP are Hard" , - , rowspan="2" , 2019 , , Jason Li (

CMU Carnegie Mellon University (CMU) is a private research university in Pittsburgh, Pennsylvania, United States. The institution was established in 1900 by Andrew Carnegie as the Carnegie Technical Schools. In 1912, it became the Carnegie Institut ...

) , , "Faster Minimum k-cut of a Simple Graph" , - , , Josh Alman (

)
Lijie Chen (

) , , "Efficient Construction of Rigid Matrices Using an NP Oracle" , - , rowspan="2" , 2018 , , Shuichi Hirahara (

The University of Tokyo The University of Tokyo (, abbreviated as in Japanese and UTokyo in English) is a public research university in Bunkyō, Tokyo, Japan. Founded in 1877 as the nation's first modern university by the merger of several pre-westernisation era ins ...

) , , "Non-black-box Worst-case to Average-case Reductions within NP" , - , , Urmila Mahadev (

UC Berkeley The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California), is a public land-grant research university in Berkeley, California, United States. Founded in 1868 and named after the Anglo-Irish philosopher George Berkele ...

) , , "Classical Verification of Quantum Computation" , - , 2017 , , Rasmus Kyng (

Yale Yale University is a private Ivy League research university in New Haven, Connecticut, United States. Founded in 1701, Yale is the third-oldest institution of higher education in the United States, and one of the nine colonial colleges ch ...

)
Peng Zhang (

Georgia Tech The Georgia Institute of Technology (commonly referred to as Georgia Tech, GT, and simply Tech or the Institute) is a public research university and institute of technology in Atlanta, Georgia, United States. Established in 1885, it has the lar ...

) , , "Hardness Results for Structured Linear Systems" , - , rowspan="2" , 2016 , , Michael B. Cohen (

) , , "Ramanujan Graphs in Polynomial Time" , - , , Aviad Rubinstein (Berkeley) , , "Settling the Complexity of Computing Approximate Two-Player Nash Equilibria" , - , rowspan="2" , 2015 , , Mika Göös (

University of Toronto The University of Toronto (UToronto or U of T) is a public university, public research university whose main campus is located on the grounds that surround Queen's Park (Toronto), Queen's Park in Toronto, Ontario, Canada. It was founded by ...

) , , "Lower Bounds for Clique vs. Independent Set" , - , , Aaron Sidford (

)
Yin Tat Lee (

)
Sam Chiu-wai Wong (

University of California, Berkeley The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California), is a Public university, public Land-grant university, land-grant research university in Berkeley, California, United States. Founded in 1868 and named after t ...

) , , "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 (

) , , "Nearly Maximum Flows in Nearly Linear Time" {{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 , - , 2012 , , Nir Bitansky (

Tel Aviv University Tel Aviv University (TAU) is a Public university, public research university in Tel Aviv, Israel. With over 30,000 students, it is the largest university in the country. Located in northwest Tel Aviv, the university is the center of teaching and ...

),
Omer Paneth (

Boston University Boston University (BU) is a Private university, private research university in Boston, Massachusetts, United States. BU was founded in 1839 by a group of Boston Methodism, Methodists with its original campus in Newbury (town), Vermont, Newbur ...

) , , "From the Impossibility of Obfuscation to a New Non-Black-Box Simulation Technique" , - , rowspan="2" , 2011 , , Kasper Green Larsen (

Aarhus Aarhus (, , ; officially spelled Århus from 1948 until 1 January 2011) is the second-largest city in Denmark and the seat of Aarhus municipality, Aarhus Municipality. It is located on the eastern shore of Jutland in the Kattegat sea and app ...

) , , "On Range Searching in the Group Model and Combinatorial Discrepancy" , - , , Timon Hertli (

ETH Zurich ETH Zurich (; ) is a public university in Zurich, Switzerland. Founded in 1854 with the stated mission to educate engineers and scientists, the university focuses primarily on science, technology, engineering, and mathematics. ETH Zurich ran ...

) , , "3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General" , - , 2010 , , Aaron Potechin (

) , , "Bounds on Monotone Switching Networks for Directed Connectivity" , - , rowspan="2" , 2009 , , Alexander Sherstov (

UT Austin The University of Texas at Austin (UT Austin, UT, or Texas) is a public university, public research university in Austin, Texas, United States. Founded in 1883, it is the flagship institution of the University of Texas System. With 53,082 stud ...

) , , "The intersection of two halfspaces has high threshold degree" , - , , Jonah Sherman (

) , , "Breaking the Multicommodity Flow Barrier for sqrt(log(n))-Approximations to Sparsest Cut" , - , 2008 , , Mihai Pătraşcu (

) , , "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 Toronto ( , locally pronounced or ) is the List of the largest municipalities in Canada by population, most populous city in Canada. It is the capital city of the Provinces and territories of Canada, Canadian province of Ontario. With a p ...

) , "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 Warsaw, officially the Capital City of Warsaw, is the capital and List of cities and towns in Poland, largest city of Poland. The metropolis stands on the Vistula, River Vistula in east-central Poland. Its population is officially estimated at ...

),
Piotr Sankowski (Warsaw) , "Maximum Matchings via Gaussian Elimination" , - , 2003 , ,

Subhash Khot Subhash Khot (born 10 June 1978 in Ichalkaranji) is an Indian-American mathematician and theoretical computer scientist who is the Julius Silver Professor of Computer Science in the Courant Institute of Mathematical Sciences at New York Uni ...

(

Princeton Princeton University is a private Ivy League research university in Princeton, New Jersey, United States. Founded in 1746 in Elizabeth as the College of New Jersey, Princeton is the fourth-oldest institution of higher education in the Unit ...

) , "Hardness of Approximating the Shortest Vector Problem in High Lp Norms" , - , rowspan="2" , 2002 , , Boaz Barak (

Weizmann Weizmann or Weizman is a surname. Notable people with this surname include: * Chaim Weizmann, a chemist, statesman, President of the World Zionist Organization, first President of Israel and founder of a research institute in Israel which eventually ...

) , "Constant-Round Coin-Tossing With a Man in the Middle or Realizing Shared Random String Model" , - , , Harald Räcke (

Paderborn Paderborn (; Westphalian language, Westphalian: ''Patterbuorn'', also ''Paterboärn'') is a city in eastern North Rhine-Westphalia, Germany, capital of the Paderborn (district), Paderborn district. The name of the city derives from the river Pade ...

) , "Minimizing Congestion in General Networks" , - , rowspan="2" , 2001 , , Boaz Barak (Weizmann) , , "How To Go Beyond the Black-Box Simulation Barrier" , - , , Vladlen Koltun (

Tel Aviv Tel Aviv-Yafo ( or , ; ), sometimes rendered as Tel Aviv-Jaffa, and usually referred to as just Tel Aviv, is the most populous city in the Gush Dan metropolitan area of Israel. Located on the Israeli Mediterranean coastline and with a popula ...

) , "Almost Tight Upper Bounds for Vertical Decompositions in Four Dimensions" , - , 2000 , ,

Piotr Indyk Piotr Indyk is Thomas D. and Virginia W. Cabot Professor in the Theory of Computation Group at the Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology. Academic biography Indyk received the Magister (M ...

(

Stanford Leland Stanford Junior University, commonly referred to as Stanford University, is a private research university in Stanford, California, United States. It was founded in 1885 by railroad magnate Leland Stanford (the eighth governor of and th ...

) , "Stable Distributions, Pseudorandom Generators, Embeddings and Data Stream Computation" , - , rowspan="2" , 1999 , , Markus Bläser (

Bonn Bonn () is a federal city in the German state of North Rhine-Westphalia, located on the banks of the Rhine. With a population exceeding 300,000, it lies about south-southeast of Cologne, in the southernmost part of the Rhine-Ruhr region. This ...

) , "A 5/2 n²-Lower Bound for the Rank of n×n Matrix Multiplication over Arbitrary Fields" , - , , Eric Vigoda (

Berkeley Berkeley most often refers to: *Berkeley, California, a city in the United States **University of California, Berkeley, a public university in Berkeley, California *George Berkeley (1685–1753), Anglo-Irish philosopher Berkeley may also refer to ...

) , "Improved Bounds for Sampling Colorings" , - , rowspan="2" , 1998 , , Kamal Jain (

) , "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 (

) , "A Random Sampling Based Algorithm for Learning the Intersection of Half-spaces" , - , 1996 , ,

Jon Kleinberg Jon Michael Kleinberg (born 1971) is an American computer scientist and the Tisch University Professor of Computer Science and Information Science at Cornell University known for his work in algorithms and networks. He is a recipient of the Nevan ...

(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 Chicago is the List of municipalities in Illinois, most populous city in the U.S. state of Illinois and in the Midwestern United States. With a population of 2,746,388, as of the 2020 United States census, 2020 census, it is the List of Unite ...

) , "Spectral Methods for Matrix Rigidity with Applications to Size-Depth Tradeoffs and Communication Complexity" , - , rowspan="2" , 1994 , , Rakesh K. Sinha,
T.S. Jayram (

Washington Washington most commonly refers to: * George Washington (1732–1799), the first president of the United States * Washington (state), a state in the Pacific Northwest of the United States * Washington, D.C., the capital of the United States ** A ...

) , "Efficient Oblivious Branching Programs for Threshold Functions" , - , , Jeffrey C. Jackson (

) , "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 The Free University of Berlin (, often abbreviated as FU Berlin or simply FU) is a public university, public research university in Berlin, Germany. It was founded in West Berlin in 1948 with American support during the early Cold War period a ...

) , "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 Rutgers University ( ), officially Rutgers, The State University of New Jersey, is a public land-grant research university consisting of three campuses in New Jersey. Chartered in 1766, Rutgers was originally called Queen's College and was aff ...

) , , "Better Bounds for Threshold Formulas" , - , 1990 , , David Zuckerman (Berkeley) , , "General weak random sources" , - , 1989 , ,

Bonnie Berger Bonnie Anne Berger (born ) is an American mathematician and computer scientist, who works as the Simons professor of mathematics and professor of electrical engineering and computer science at the Massachusetts Institute of Technology. She is the ...

(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 John F. Canny (born in 1958) is an Australian computer scientist, and ''Paul E. Jacobs, Paul E Jacobs and Stacy Jacobs Distinguished Professor of Engineering'' in the Computer Science Department of the University of California, Berkeley. He has m ...

(MIT) , , "A New Algebraic Method for Robot Motion Planning and Real Geometry" , - , , Abhiram G. Ranade (

) , , "How to Emulate Shared Memory (Preliminary Version)" , - , 1986 , ,

Prabhakar Raghavan Prabhakar Raghavan is a computer scientist and the Chief Technologist at Google. His research spans algorithms, web search and databases. He is the co-author of the textbooks ''Randomized Algorithms'' with Rajeev Motwani and ''Introduction to Info ...

(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 George Mairson is a theoretical computer scientist and professor of computer science in thVolen National Center for Complex Systemsat Brandeis University in Waltham, Massachusetts. His research is in the fields of logic in computer science, l ...

(Stanford) , , "The Program Complexity of Searching a Table" , - , 1982 , , Carl Sturtivant (

University of Minnesota The University of Minnesota Twin Cities (historically known as University of Minnesota) is a public university, public Land-grant university, land-grant research university in the Minneapolis–Saint Paul, Twin Cities of Minneapolis and Saint ...

) , , "Generalized Symmetries of Polynomials in Algebraic Complexity" , - , 1981 , , F. Thomson Leighton (MIT) , , "New Lower Bound Techniques for VLSI"

References

Awards established in 1981 Computer science awards IEEE awards Student awards

Past recipients

See also

References