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 , - , 2021 , , Xiao Mao (

MIT The Massachusetts Institute of Technology (MIT) is a private land-grant research university in Cambridge, Massachusetts. Established in 1861, MIT has played a key role in the development of modern technology and science, and is one of the mo ...

) , , "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) , , "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 , abbreviated as or UTokyo, is a public research university located in Bunkyō, Tokyo, Japan. Established in 1877, the university was the first Imperial University and is currently a Top Type university of the Top Global University Project by ...

) , , "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 university, public land-grant university, land-grant research university in Berkeley, California. Established in 1868 as the University of Californi ...

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

Yale Yale University is a private research university in New Haven, Connecticut. Established in 1701 as the Collegiate School, it is the third-oldest institution of higher education in the United States and among the most prestigious in the wor ...

)
Peng Zhang (

Georgia Tech The Georgia Institute of Technology, commonly referred to as Georgia Tech or, in the state of Georgia, as Tech or The Institute, is a public research university and institute of technology in Atlanta, Georgia. Established in 1885, it is part of ...

) , , "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 research university in Toronto, Ontario, Canada, located on the grounds that surround Queen's Park. It was founded by royal charter in 1827 as King's College, the first institution ...

) , , "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 land-grant research university in Berkeley, California. Established in 1868 as the University of California, it is the state's first land-grant u ...

) , , "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) ( he, אוּנִיבֶרְסִיטַת תֵּל אָבִיב, ''Universitat Tel Aviv'') is a public research university in Tel Aviv, Israel. With over 30,000 students, it is the largest university in the country. Locate ...

),
Omer Paneth (

Boston University Boston University (BU) is a private research university in Boston, Massachusetts. The university is nonsectarian, but has a historical affiliation with the United Methodist Church. It was founded in 1839 by Methodists with its original campu ...

) , , "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. It is located on the eastern shore of Jutland in the Kattegat sea and approximately northwest ...

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

ETH Zurich (colloquially) , former_name = eidgenössische polytechnische Schule , image = ETHZ.JPG , image_size = , established = , type = Public , budget = CHF 1.896 billion (2021) , rector = Günther Dissertori , president = Joël Mesot , ac ...

) , , "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 research university in Austin, Texas. It was founded in 1883 and is the oldest institution in the University of Texas System. With 40,916 undergraduate students, 11,075 ...

) , , "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 KTH may refer to: * Keat Hong LRT station, Singapore, LRT station abbreviation * Kent House railway station, London, National Rail station code * KTH Royal Institute of Technology, a university in Sweden * KTH Krynica, a Polish ice hockey team * Khy ...

) , "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 ( ; or ) is the capital city of the Canadian province of Ontario. With a recorded population of 2,794,356 in 2021, it is the most populous city in Canada and the fourth most populous city in North America. The city is the ancho ...

) , "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 ( pl, Warszawa, ), officially the Capital City of Warsaw,, abbreviation: ''m.st. Warszawa'' is the capital and largest city of Poland. The metropolis stands on the River Vistula in east-central Poland, and its population is officia ...

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

Subhash Khot Subhash Khot (born June 10, 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 Univers ...

(

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

) , "Hardness of Approximating the Shortest Vector Problem in High Lp Norms" , - , rowspan="2" , 2002 , , Boaz Barak ( Weizmann) , "Constant-Round Coin-Tossing With a Man in the Middle or Realizing Shared Random String Model" , - , , Harald Räcke (

Paderborn Paderborn (; Westphalian: ''Patterbuorn'', also ''Paterboärn'') is a city in eastern North Rhine-Westphalia, Germany, capital of the Paderborn district. The name of the city derives from the river Pader and ''Born'', an old German term for t ...

) , "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 ( he, תֵּל־אָבִיב-יָפוֹ, translit=Tēl-ʾĀvīv-Yāfō ; ar, تَلّ أَبِيب – يَافَا, translit=Tall ʾAbīb-Yāfā, links=no), often referred to as just Tel Aviv, is the most populous city in the G ...

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

(

Stanford Stanford University, officially Leland Stanford Junior University, is a private research university in Stanford, California. The campus occupies , among the largest in the United States, and enrolls over 17,000 students. Stanford is considere ...

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

Bonn The federal city of Bonn ( lat, Bonna) is a city on the banks of the Rhine in the German state of North Rhine-Westphalia, with a population of over 300,000. About south-southeast of Cologne, Bonn is in the southernmost part of the Rhine-Ruhr r ...

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

) , "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 Santosh Vempala (born 18 October 1971) is a prominent computer scientist. He is a Distinguished Professor of Computer Science at the Georgia Institute of Technology. His main work has been in the area of Theoretical Computer Science. Biography ...

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

(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 (''City in a Garden''); I Will , image_map = , map_caption = Interactive Map of Chicago , coordinates = , coordinates_footnotes = , subdivision_type = Country , subdivision_name ...

) , "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 commonly refers to: * Washington (state), United States * Washington, D.C., the capital of the United States ** A metonym for the federal government of the United States ** Washington metropolitan area, the metropolitan area centered on ...

) , "Efficient Oblivious Branching Programs for Threshold Functions" , - , , 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 The Free University of Berlin (, often abbreviated as FU Berlin or simply FU) is a public research university in Berlin, Germany. It is consistently ranked among Germany's best universities, with particular strengths in political science and t ...

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

) , , "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 Shmuel Safra ( he, שמואל ספרא) is an Israeli computer scientist. He is a Professor of Computer Science at Tel Aviv University, Israel. He was born in Jerusalem. Safra's research areas include Computational complexity theory, complexity ...

(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 and Stacy Jacobs Distinguished Professor of Engineering'' in the Computer Science Department of the University of California, Berkeley. He has made significant ...

(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 (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, ...

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

University of Minnesota The University of Minnesota, formally the University of Minnesota, Twin Cities, (UMN Twin Cities, the U of M, or Minnesota) is a public university, public Land-grant university, land-grant research university in the Minneapolis–Saint Paul, Tw ...

) , , "Generalized Symmetries of Polynomials in Algebraic Complexity" , - , 1981 , ,

F. Thomson Leighton Frank Thomson "Tom" Leighton (born 1956) is the CEO of Akamai Technologies, the company he co-founded with the late Daniel Lewin in 1998.Erik Nygren, Ramesh Sitaraman, and Jennifer Sun. As one of the world's preeminent authorities on algorithms ...

(MIT) , , "New Lower Bound Techniques for VLSI"

References

Awards established in 1981 Computer science awards IEEE awards Student awards

Past recipients

See also

References