The Machtey Award is awarded at the annual IEEE Symposium on Foundations of Computer Science (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. [1] The counterpart of this award at the ACM Symposium on Theory of Computing (STOC) is the Danny Lewin Best Student Paper Award. [2]
Past recipients of the Machtey award are tabulated below.[ citation needed ]
Year | Recipient (University) | Paper |
---|---|---|
2021 | Xiao Mao (MIT) | "Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance" |
2020 | Rahul Ilango (MIT) | "The Constant Depth Formula and Partial Function Versions of MCSP are Hard" |
2019 | Jason Li (CMU) | "Faster Minimum k-cut of a Simple Graph" |
Josh Alman (MIT) Lijie Chen (MIT) | "Efficient Construction of Rigid Matrices Using an NP Oracle" | |
2018 | Shuichi Hirahara (The University of Tokyo) | "Non-black-box Worst-case to Average-case Reductions within NP" |
Urmila Mahadev (UC Berkeley) | "Classical Verification of Quantum Computation" | |
2017 | Rasmus Kyng (Yale) Peng Zhang (Georgia Tech) | "Hardness Results for Structured Linear Systems" [3] |
2016 | Michael B. Cohen (MIT) | "Ramanujan Graphs in Polynomial Time" [4] |
Aviad Rubinstein (Berkeley) | "Settling the Complexity of Computing Approximate Two-Player Nash Equilibria" [5] | |
2015 | Mika Göös (University of Toronto) | "Lower Bounds for Clique vs. Independent Set" |
Aaron Sidford (MIT) Yin Tat Lee (MIT) Sam Chiu-wai Wong (University of California, Berkeley) | "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 (University of California, Berkeley) | "Nearly Maximum Flows in Nearly Linear Time" [6] |
2012 | Nir Bitansky (Tel Aviv University), Omer Paneth (Boston University) | "From the Impossibility of Obfuscation to a New Non-Black-Box Simulation Technique" |
2011 | Kasper Green Larsen (Aarhus) | "On Range Searching in the Group Model and Combinatorial Discrepancy" |
Timon Hertli (ETH Zurich) | "3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General" | |
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) | "Breaking the Multicommodity Flow Barrier for sqrt(log(n))-Approximations to Sparsest Cut" | |
2008 | Mihai Pătraşcu (MIT) | "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" |
2005 | Mark Braverman (Toronto) | "On the Complexity of Real Functions" |
Tim Abbott (MIT), Daniel Kane (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" |
Harald Räcke (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 Bläser (Bonn) | "A 5/2 n2-Lower Bound for the Rank of n×n Matrix Multiplication over Arbitrary Fields" |
Eric Vigoda (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, T.S. Jayram (Washington) | "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) | "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 | Bonnie Berger (MIT) John Rompel (MIT) | "Simulating (logcn)-wise independence in NC" |
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 (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 (Stanford) | "The Program Complexity of Searching a Table" |
1982 | Carl Sturtivant (University of Minnesota) | "Generalized Symmetries of Polynomials in Algebraic Complexity" |
1981 | F. Thomson Leighton (MIT) | "New Lower Bound Techniques for VLSI" |
Daniel Mark Lewin, sometimes spelled Levin, was an American–Israeli mathematician and entrepreneur who co-founded internet company Akamai Technologies. A passenger on board American Airlines Flight 11, it is believed that Lewin was stabbed to death by one of the hijackers of that flight, and was the first victim of the September 11th attacks.
ACM SIGACT or SIGACT is the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory, whose purpose is support of research in theoretical computer science. It was founded in 1968 by Patrick C. Fischer.
Harry George Mairson is a theoretical computer scientist and Professor of Computer Science in the Volen National Center for Complex Systems 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, computational complexity theory, and algorithmics.
Daniel Mertz Kane is an American mathematician. He is currently an associate professor with a joint position in the Mathematics Department and the Computer Science and Engineering Department at the University of California, San Diego.
Scott Joel Aaronson is an American theoretical computer scientist and David J. Bruton Jr. Centennial Professor of Computer Science at the University of Texas at Austin. His primary areas of research are quantum computing and computational complexity theory.
John F. Canny 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 contributions in various areas of computer science and mathematics, including artificial intelligence, robotics, computer graphics, human-computer interaction, computer security, computational algebra, and computational geometry.
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 Computing Machinery special interest group SIGACT. Acceptance rate of STOC, averaged from 1970 to 2012, is 31%, with the rate of 29% in 2012.
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.
Luca Trevisan is an Italian professor of computer science at Bocconi University in Milan.
Ran Raz is a computer scientist who works in the area of computational complexity theory. He was a professor in the faculty of mathematics and computer science at the Weizmann Institute. He is now a professor of computer science at Princeton University.
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.
The Kleene Award is awarded at the annual IEEE Symposium on Logic in Computer Science (LICS) to the author(s) of the best student paper(s). A paper qualifies as a student paper if each author is a student at the date of the submission. Also eligible are authors who have graduated only recently, provided the submitted paper is based on work carried out when he or she still was a student. The award decision is made by the Program Committee.
Prabhakar Raghavan is a Senior Vice President at Google, where he is responsible for Google Search, Assistant, Geo, Ads, Commerce, and Payments products. His research spans algorithms, web search and databases and he is the co-author of the textbooks Randomized Algorithms with Rajeev Motwani and Introduction to Information Retrieval.
Mordechai M. "Moti" Yung is a cryptographer and computer scientist known for his work on cryptovirology and kleptography.
Mihai Pătrașcu was a Romanian-American computer scientist at AT&T Labs in Florham Park, New Jersey, USA.
Timothy Avelin Roughgarden is an American computer scientist and a Professor of Computer Science at Columbia University. Roughgarden's work deals primarily with game theoretic questions in computer science.
Jaikumar Radhakrishnan is an Indian computer scientist specialising in combinatorics and communication complexity. He has served as dean of the School of Technology and Computer Science at the Tata Institute of Fundamental Research, Mumbai, India, where he is currently a senior professor.
Amit Sahai is an American computer scientist. He is a professor of computer science at UCLA and the director of the Center for Encrypted Functionalities.
Kasper Green Larsen is a Danish theoretical computer scientist. He is currently full professor at Aarhus University.
Michael A. Bender is an American computer scientist, known for his work in cache-oblivious algorithms, lowest common ancestor data structures, scheduling (computing), and pebble games. He is David R. Smith Leading Scholar professor of computer science at Stony Brook University, and a co-founder of storage technology startup company Tokutek.