Machtey Award
From Wikipedia, the free encyclopedia
The Machtey Award is awarded at the annual IEEE Symposium on Foundations of 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.[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
Past recipients of the Machtey award are tabulated below.[citation needed]
| Year | Recipient (University) | Paper |
|---|---|---|
| 2013 | Jonah Sherman (University of California, Berkeley) | "Nearly Maximum Flows in Nearly Linear Time" [3] |
| 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" |
| 1993 | ? | |
| 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 | ? | |
| 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" |
See also
References
- ↑ List of publications by Michael Machtey
- ↑ ACM SIGACT. "Danny Lewin Best Student Paper Award"
- ↑ "FOCS 2013 Best Paper Awards".
This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.