Machtey Award - Machtey Award
 | tento článek příliš spoléhá na Reference na primární zdroje. (Leden 2020) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) |
The Machtey Award je udělován na každoročním IEEE Symposium on Foundations of Computer Science (FOCS) autorům nejlepších studentských prací. Příspěvek se kvalifikuje jako studentský příspěvek, pokud jsou všichni autoři k datu odevzdání studenti na plný úvazek. O udělení ceny rozhoduje programový výbor.
Tato cena je pojmenována po Michaelovi Machteyovi, který byl v 70. letech výzkumným pracovníkem v komunitě teoretických informatik.[1] Protějšek tohoto ocenění na ACM Symposium on Theory of Computing (STOC) je Cena za nejlepší studentský papír Dannyho Lewina.[2]
Minulí příjemci
Minulí příjemci ceny Machtey jsou uvedeny v tabulce níže.[Citace je zapotřebí ]
| Rok | Příjemce (univerzita) | Papír |
|---|---|---|
| 2019 | Jason Li (CMU ) | "Rychlejší minimální k-řez jednoduchého grafu." |
| Josh Alman (MIT ) Lijie Chen (MIT ) | „Efektivní konstrukce tuhých matic pomocí NP Oracle“ | |
| 2018 | Shuichi Hirahara (Tokijská univerzita ) | „Non-black-box Worst-case to Average-case Reductions within NP“ |
| Urmila Mahadev (UC Berkeley ) | „Klasické ověření kvantového výpočtu“ | |
| 2017 | Rasmus Kyng (Yale ) Peng Zhang (Georgia Tech ) | "Výsledky tvrdosti pro strukturované lineární systémy"[3] |
| 2016 | Michael B.Cohen (MIT ) | "Ramanujan Graphs in Polynomial Time"[4] |
| Aviad Rubinstein (Berkeley) | „Řešení složitosti výpočtu přibližné rovnováhy Nash pro dva hráče“[5] | |
| 2015 | Mika Göös (University of Toronto ) | „Dolní hranice pro Clique vs. Independent Set“ |
| Aaron Sidford (MIT ) Yin Tat Lee (MIT ) Sam Chiu-wai Wong (University of California, Berkeley ) | „Rychlejší metoda roviny řezu a její důsledky pro kombinatorickou a konvexní optimalizaci“ | |
| 2014 | Aaron Sidford (MIT) Yin Tat Lee (MIT) | „Metody hledání trasy pro lineární programování: Řešení lineárních programů v Õ (√rank) iteracích a rychlejší algoritmy pro maximální tok |
| 2013 | Jonah Sherman (University of California, Berkeley ) | „Téměř maximální průtok v téměř lineárním čase“ [6] |
| 2012 | Nir Bitansky (Tel Avivská univerzita ), Omer Paneth (Bostonská univerzita ) | „Od nemožnosti zmatku k nové simulační technice jiné než černé skříňky“ |
| 2011 | Kasper Green Larsen (Aarhus ) | „Vyhledávání v rozsahu ve skupinovém modelu a kombinatorická nesrovnalost“ |
| Timon Hertli (ETH Curych ) | „Rychlejší a jednodušší 3 SAT - jedinečné hranice SAT pro PPSZ Hold obecně“ | |
| 2010 | Aaron Potechin (MIT ) | „Hranice v monotónních přepínacích sítích pro přímé připojení“ |
| 2009 | Alexander Sherstov (UT Austin ) | „Křižovatka dvou poloprostorů má vysoký prahový stupeň“ |
| Jonah Sherman (University of California, Berkeley ) | „Prolomení bariéry toku více akomodit pro sqrt (log (n)) - aproximace nejsparsnějšího řezu“ | |
| 2008 | Mihai Pătraşcu (MIT ) | „Succincter“ |
| 2007 | Per Austrin (KTH ) | „Směrem k ostré nepřístupnosti pro jakýkoli 2-CSP“ |
| 2006 | Nicholas J. A. Harvey (MIT) | „Algebraické struktury a algoritmy pro porovnávání a problémy matroidů“ |
| 2005 | Mark Braverman (Toronto ) | „O složitosti skutečných funkcí“ |
| Tim Abbott (MIT), Daniel Kane (MIT), | „O složitosti her pro dva hráče, které prohrají“ | |
| 2004 | Lap Chi Lau (Toronto) | „Přibližná věta o Max-Steinerově-stromovém balení o Min-Steinerově řezu“ |
| Marcin Mucha (Varšava ), Piotr Sankowski (Varšava) | „Maximum Matchings via Gaussian Elimination“ | |
| 2003 | Subhash Khot (Princeton ) | „Tvrdost aproximace nejkratšího vektorového problému ve vysokých normách Lp“ |
| 2002 | Boaz Barak (Weizmann ) | „Házení mincí s mužem ve středu nebo realizace sdíleného modelu náhodných řetězců“ |
| Harald Räcke (Paderborn ) | „Minimalizace zahlcení v obecných sítích“ | |
| 2001 | Boaz Barak (Weizmann) | „How to Go Beyond the the Black-Box Simulation Barrier“ |
| Vladlen Koltun (Tel Aviv ) | „Téměř těsné horní hranice pro vertikální rozklady ve čtyřech rozměrech“ | |
| 2000 | Piotr Indyk (Stanford ) | "Stabilní distribuce, pseudonáhodné generátory, vkládání a výpočet datového proudu" |
| 1999 | Markus Bläser (Bonn ) | „A 5/2 n2- Dolní hranice pro hodnost n × n násobení matic přes libovolná pole " |
| Eric Vigoda (Berkeley ) | "Vylepšené hranice pro vzorkování barvení" | |
| 1998 | Kamal Jain (Georgia Tech ) | „Aproximační algoritmus faktoru 2 pro zobecněný problém Steinerovy sítě“ |
| Daniele Micciancio (MIT) | „Nejkratší vektorový problém je NP těžko aproximovatelný v rámci nějaké konstanty“ | |
| 1997 | Santosh Vempala (CMU ) | „Algoritmus náhodného vzorkování pro učení průniku poloprostorů“ |
| 1996 | Jon Kleinberg (MIT) | „Jednodílný nerozdělitelný tok“ |
| 1995 | Andras Benczur (MIT) | „Reprezentace řezů v rámci 6/5násobné konektivity s aplikacemi“ |
| Satyanarayana V. Lokam (Chicago ) | „Spektrální metody pro tuhost matice s aplikacemi na kompromisy podle velikosti a hloubky komunikace“ | |
| 1994 | Rakesh K. Sinha, T.S. Jayram (Washington ) | „Efektivní nepostradatelné programy větvení prahových funkcí“ |
| Jeffrey C. Jackson (CMU ) | „Efektivní algoritmus dotazu na členství pro učení DNF s ohledem na jednotnou distribuci“ | |
| 1993 | Pascal Koiran | „Slabá verze modelu Blum, Shub & Smale“ |
| 1992 | Bernd Gärtner (FU Berlín ) | „Subexponenciální algoritmus pro problémy s optimalizací abstraktů“ |
| 1991 | Anna Gal (Chicago) | „Dolní hranice pro složitost spolehlivých booleovských obvodů s hlučnými branami“ |
| Jaikumar Radhakrishnan (Rutgers ) | „Lepší hranice pro prahové vzorce“ | |
| 1990 | David Zuckerman (Berkeley) | „Obecné slabé náhodné zdroje“ |
| 1989 | Bonnie Berger (MIT) John Rompel (MIT) | "Simulace (logC n) - nezávislost v NC " |
| 1988 | Shmuel Safra (Weizmann) | „O složitosti omega-automatů“ |
| 1987 | John Canny (MIT) | „Nová algebraická metoda pro plánování pohybu robota a skutečnou geometrii“ |
| Abhiram G. Ranade (Yale ) | „Jak emulovat sdílenou paměť (předběžná verze)“ | |
| 1986 | Prabhakar Raghavan (Berkeley) | „Pravděpodobnostní konstrukce deterministických algoritmů: přibližné balení celočíselných programů“ |
| 1985 | Ravi B. Boppana (MIT) | „Zesílení pravděpodobnostních logických vzorců“ |
| 1984 | Joel Friedman (Harvard) | "Konstrukce O (n log n) Velikost monotónních vzorců pro k-tý elementární symetrický polynom z n Booleovské proměnné " |
| 1983 | Harry Mairson (Stanford) | „Programová složitost prohledávání tabulky“ |
| 1982 | Carl Sturtivant (University of Minnesota ) | "Zobecněné symetrie polynomů v algebraické složitosti" |
| 1981 | F. Thomson Leighton (MIT) | „Nové dolně vázané techniky pro VLSI“ |
Viz také
Reference
- ^ Seznam publikací Michaela Machteye
- ^ ACM SIGACT. „Cena za nejlepší studentský papír Dannyho Lewina“ Archivováno 20. června 2008, v Wayback Machine
- ^ „Ocenění FOCS 2017 za nejlepší papír“ (PDF).
- ^ „Ocenění FOCS 2016 za nejlepší papír“ (PDF).
- ^ „Ocenění FOCS 2016 za nejlepší papír“ (PDF).
- ^ „Ocenění FOCS 2013 za nejlepší papír“. Archivovány od originál dne 2013-12-13. Citováno 2013-12-06.