Machtey Award
Machtey Award delas ut vid det årliga IEEE Symposium on Foundations of Computer Science (FOCS) till författaren/författarna till den/de bästa studentuppsatsen. En uppsats kvalificeras som studentuppsats om alla författare är heltidsstudenter vid inlämningsdatumet. Tilldelningsbeslutet fattas av programnämnden.
Priset är uppkallat efter Michael Machtey, som var forskare inom det teoretiska datavetenskapliga samhället på 1970-talet. Motsvarigheten till denna utmärkelse vid ACM Symposium on Theory of Computing (STOC) är Danny Lewin Best Student Paper Award .
Tidigare mottagare
Tidigare mottagare av Machtey-utmärkelsen listas nedan. [ citat behövs ]
| År | Mottagare (universitet) | Papper |
|---|---|---|
| 2021 | Xiao Mao ( MIT ) | "Att bryta den kubiska barriären för (oviktad) trädredigeringsavstånd" |
| 2020 | Rahul Ilango ( MIT ) | "Constant Depth Formel och Partial Function versioner av MCSP är svåra" |
| 2019 | Jason Li ( CMU ) | "Snabbare minsta k-snitt av en enkel graf" |
|
Josh Alman ( MIT ) Lijie Chen ( MIT ) |
"Effektiv konstruktion av stela matriser med hjälp av ett NP-orakel" | |
| 2018 | Shuichi Hirahara ( Universitetet i Tokyo ) | "Icke-black box Minskningar från värsta till genomsnittliga fall inom NP" |
| Urmila Mahadev ( UC Berkeley ) | "Klassisk verifiering av kvantberäkning" | |
| 2017 |
Rasmus Kyng ( Yale ) Peng Zhang ( Georgia Tech ) |
"Hårdhetsresultat för strukturerade linjära system" |
| 2016 | Michael B. Cohen ( MIT ) | "Ramanujan-grafer i polynomisk tid" |
| Aviad Rubinstein (Berkeley) | "Att lösa komplexiteten i att beräkna ungefärlig Nash-jämvikt för två spelare" | |
| 2015 | Mika Göös ( University of Toronto ) | "Lägre gränser för klick vs. oberoende set" |
|
Aaron Sidford ( MIT ) Yin Tat Lee ( MIT ) Sam Chiu-wai Wong ( University of California, Berkeley ) |
"En snabbare skärplansmetod och dess konsekvenser för kombinatorisk och konvex optimering" | |
| 2014 |
Aaron Sidford (MIT) Yin Tat Lee (MIT) |
"Vägsökningsmetoder för linjär programmering: Lösning av linjära program i Õ(√rank) iterationer och snabbare algoritmer för maximalt flöde" |
| 2013 | Jonah Sherman ( University of California, Berkeley ) | "Nästan maximala flöden på nästan linjär tid" |
| 2012 |
Nir Bitansky ( Tel Aviv University ), Omer Paneth ( Boston University ) |
"Från omöjligheten att fördunkla till en ny simuleringsteknik utan svart box" |
| 2011 | Kasper Green Larsen ( Århus ) | "Om intervallsökning i gruppmodellen och kombinatorisk diskrepans" |
| Timon Hertli ( ETH Zürich ) | "3-SAT snabbare och enklare - Unika-SAT-gränser för PPSZ Hold i allmänhet" | |
| 2010 | Aaron Potechin ( MIT ) | "Gränser för monotonväxlingsnätverk för riktad anslutning" |
| 2009 | Alexander Sherstov ( UT Austin ) | "Skärningen mellan två halvrum har hög tröskelgrad" |
| Jonah Sherman ( University of California, Berkeley ) | "Att bryta multicommodity flödesbarriären för sqrt(log(n))-Approximations to Sparsest Cut" | |
| 2008 | Mihai Pătraşcu ( MIT ) | "Succincter" |
| 2007 | Per Austrin ( KTH ) | "Mot skarp otillräcklighet för alla 2-CSP" |
| 2006 | Nicholas JA Harvey (MIT) | "Algebraiska strukturer och algoritmer för matchnings- och matroidproblem" |
| 2005 | Mark Braverman ( Toronto ) | "Om de verkliga funktionernas komplexitet" |
| Tim Abbott (MIT),
|
"Om komplexiteten hos två spelare vinna-förlust-spel" | |
| 2004 | Lap Chi Lau (Toronto) | "En ungefärlig Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem" |
| Marcin Mucha ( Warszawa ), Piotr Sankowski (Warszawa) |
"Maximala matchningar via Gaussisk eliminering" | |
| 2003 | Subhash Khot ( Princeton ) | "Hårdhet att approximera det kortaste vektorproblemet i höga Lp-normer" |
| 2002 | Boaz Barak ( Weizmann ) | "Konstant-runda myntkastning med en man i mitten eller realisera delad slumpmässig strängmodell" |
| Harald Räcke ( Paderborn ) | "Minimera överbelastning i allmänna nätverk" | |
| 2001 | Boaz Barak (Weizmann) | "Hur går man bortom Black-Box-simuleringsbarriären" |
| Vladlen Koltun ( Tel Aviv ) | "Nästan snäva övre gränser för vertikala nedbrytningar i fyra dimensioner" | |
| 2000 | Piotr Indyk ( Stanford ) | "Stabila distributioner, pseudoslumpgeneratorer, inbäddningar och dataströmsberäkning" |
| 1999 | Markus Bläser ( Bonn ) | "A 5/2 n 2 -Nedre gräns för rangordningen av n×n matrismultiplikation över godtyckliga fält" |
| Eric Vigoda ( Berkeley ) | "Förbättrade gränser för provtagning av färger" | |
| 1998 | Kamal Jain ( Georgia Tech ) | "Faktor 2-approximationsalgoritm för det generaliserade Steiner-nätverksproblemet" |
| Daniele Micciancio (MIT) | "Det kortaste vektorproblemet är NP-svårt att approximera till inom någon konstant" | |
| 1997 | Santosh Vempala ( CMU ) | "En slumpmässig urvalsbaserad algoritm för att lära sig skärningspunkten mellan halvutrymmen" |
| 1996 | Jon Kleinberg (MIT) | "Odelat flöde med en källa" |
| 1995 | Andras Benczur (MIT) | "A representation of cuts within 6/5 Times the Edge Connectivity with Applications" |
| Satyanarayana V. Lokam ( Chicago ) | "Spektrala metoder för matrisstyvhet med tillämpningar för storleksdjupavvägningar och kommunikationskomplexitet" | |
| 1994 | Rakesh K. Sinha, TS Jayram ( Washington ) |
"Effektiva Oblivious förgreningsprogram för tröskelfunktioner" |
| Jeffrey C. Jackson ( CMU ) | "En effektiv medlemskapsfråga-algoritm för att lära sig DNF med hänsyn till den enhetliga distributionen" | |
| 1993 | Pascal Koiran | "En svag version av Blum, Shub & Smale-modellen" |
| 1992 | Bernd Gärtner ( FU Berlin ) | "En subexponentiell algoritm för abstrakta optimeringsproblem" |
| 1991 | Anna Gal (Chicago) | "Lägre gränser för komplexiteten hos pålitliga booleska kretsar med brusiga grindar" |
| Jaikumar Radhakrishnan ( Rutgers ) | "Bättre gränser för tröskelformler" | |
| 1990 | David Zuckerman (Berkeley) | "Allmänna svaga slumpmässiga källor" |
| 1989 |
Bonnie Berger (MIT) John Rompel (MIT) |
"Simulerar (log c n )-vis oberoende i NC" |
| 1988 | Shmuel Safra (Weizmann) | "Om komplexiteten i omega-Automata" |
| 1987 | John Canny (MIT) | "En ny algebraisk metod för robotrörelseplanering och verklig geometri" |
| Abhiram G. Ranade ( Yale ) | "Hur man emulerar delat minne (preliminär version)" | |
| 1986 | Prabhakar Raghavan (Berkeley) | "Probabilistisk konstruktion av deterministiska algoritmer: Approximating av heltalsprogram för packning" |
| 1985 | Ravi B. Boppana (MIT) | "Förstärkning av probabilistiska booleska formler" |
| 1984 | Joel Friedman (Harvard) | monotonformler för O( n log n ) storlek för det k -:te elementära symmetriska polynomet av n booleska variabler" |
| 1983 | Harry Mairson (Stanford) | "Programkomplexiteten i att söka i en tabell" |
| 1982 | Carl Sturtivant ( University of Minnesota ) | "Generaliserade symmetrier av polynom i algebraisk komplexitet" |
| 1981 | F. Thomson Leighton (MIT) | "Nya nedre gränstekniker för VLSI" |
Se även
- ^ Lista över publikationer av Michael Machtey på DBLP
- ^ ACM SIGACT. "Danny Lewin Best Student Paper Award" Arkiverad 20 juni 2008, på Wayback Machine
- ^ "FOCS 2017 Best Paper Awards" (PDF) .
- ^ "FOCS 2016 Best Paper Awards" (PDF) .
- ^ "FOCS 2016 Best Paper Awards" (PDF) .
- ^ "FOCS 2013 Best Paper Awards" . Arkiverad från originalet 2013-12-13 . Hämtad 2013-12-06 .