Lance Fortnow - Lance Fortnow - Wikipedia

Lance Fortnow
narozený15. srpna 1963 (1963-08-15) (stáří57)
Národnostamerický
Alma materCornell University
Massachusetts Institute of Technology
Známý jakoInteraktivní důkazy
OceněníČlen ACM, NSF Člen prezidentské fakulty, Fulbright Scholar, Cena Nerode
Vědecká kariéra
PolePočítačová věda
InstituceIllinoisský technologický institut
Georgia Tech
Northwestern University
University of Chicago
Doktorský poradceMichael Sipser
DoktorandiCarsten Lund
webová stránkahttp://lance.fortnow.com/
http://blog.computationalcomplexity.org/

Lance Jeremy Fortnow (narozen 15. srpna 1963) je a počítačový vědec známý pro hlavní výsledky v výpočetní složitost a interaktivní kontrolní systémy. V současné době je děkanem College of Science v Illinoisský technologický institut.

Životopis

Lance Fortnow získal doktorát z aplikované matematiky na MIT v roce 1989,[1] kontrolován Michael Sipser. Od ukončení studia působí na fakultě University of Chicago (1989-1999, 2003-2007), Northwestern University (2008-2012) a naposledy Gruzínský technologický institut (2012 – současnost) jako předseda School of Computer Science.[2][3]

Fortnow byl zakládajícím šéfredaktorem časopisu ACM Transactions on Computation Theory.[4] Byl předsedou ACM SIGACT[5] a uspěl Paul Beame. Byl předsedou konference IEEE o výpočetní složitosti[6] od roku 2000 do roku 2006. V roce 2003 zahájil Fortnow jeden z prvních blogů věnovaných teoretické informatice[7] a od té doby pro ni napsal; od roku 2007 má co-bloggera, William Gasarch. V září 2009 Fortnow upozornil pozornost hlavního proudu na teorii složitosti, když publikoval článek mapující pokrok dosažený v Problém P versus NP v komunikaci Asociace výpočetní techniky.[8][9]

Práce

Ve svých mnoha publikacích Fortnow přispěl důležitými výsledky do oblasti výpočetní složitost. Zatímco byl ještě absolventem MIT, Fortnow ukázal, že neexistují žádné dokonalé nulové znalosti protokoly pro NP-kompletní jazyky, pokud polynomiální hierarchie zhroutí se.[10] S Michaelem Sipserem také demonstroval, že ve vztahu ke konkrétnímu věštci existuje jazyk co-NP který nemá interaktivní protokol.[11]

V listopadu 1989 Fortnow obdržel e-mail od Noam Nisan ukazující, že co-NP měl několik prover interaktivních důkazů (MIP). S Carsten Lund a Howard Karloff, použil tento výsledek k vývoji algebraické techniky pro konstrukci interaktivních důkazních systémů a prokázání, že každý jazyk v hierarchii polynomiálního času má interaktivní důkazní systém.[12] Jejich práce byla sotva stará dva týdny Adi Shamir použil to, aby to dokázal IP =PSPACE.[13] Rychle na to navázal (17. ledna 1990, necelé dva měsíce po obdržení Nisanova e-mailu) Fortnow, spolu s László Babai a Carsten Lund to dokázali MIP =NEXP.[14] Tyto algebraické techniky dále rozšířil Fortnow, Babai, Leonid Levin, a Mario Szegedy když představili nový obecný mechanismus pro kontrolu výpočtů.[15]

Od té doby Fortnow nadále publikuje o různých tématech v oblasti výpočetní složitosti včetně derandomizace, řídké jazyky, a věštecké stroje. Fortnow také publikoval na kvantové výpočty, herní teorie, sekvenování genomu, a ekonomika.

Práce Lance Fortnow v ekonomii zahrnuje práci v teorii her, optimálních strategiích a predikcích. S Duke Whangem zkoumal Fortnow problém klasické teorie her vězňovo dilema, rozšíření problému tak, že dilema je kladeno postupně nekonečně mnohokrát. Zkoumali, jaké strategie by hráči měli vzít vzhledem k omezením, že své strategie čerpají z výpočetně ohraničených množin a zavádějí „období odkladu“, aby zabránili dominanci pomstychtivých strategií.[16] Fortnow také zkoumal logaritmický pravidlo tržního bodování (LMSR) s tvůrci trhu. Pomohl ukázat, že ceny LMSR jsou # P-tvrdé a navrhnout aproximační techniku ​​pro cenové permutační trhy.[17] Podílel se také na studii chování informovaných obchodníků pracujících s tvůrci trhu LMSR.[18]

Fortnow také napsal populárně-vědeckou knihu s názvem The Golden Ticket: P, NP and the Search for the Impossible.[19], který volně vycházel z článku, který dříve napsal pro CACM v roce 2009.[20] Fortnow ve své knize poskytuje netechnický úvod do problému P versus NP a jeho algoritmických omezení. Dále popisuje svou knihu a ilustruje, proč jsou problémy NP tak důležité na internetu Data Skeptický podcast.[21]

Ceny a vyznamenání

Reference

  1. ^ Lance Fortnow na Matematický genealogický projekt
  2. ^ „College of Computing Hires Fortnow, Anton to Lead Schools“ (Tisková zpráva). Georgia Tech College of Computing. 19. března 2012. Citováno 4. října 2012.
  3. ^ Fakulta elektrotechniky a informatiky na Northwestern University
  4. ^ Transakce ACM na základě teorie výpočtu
  5. ^ ACM SIGACT
  6. ^ Konference IEEE o výpočetní složitosti
  7. ^ Výpočetní složitost Weblog
  8. ^ J. Markoff. Kromě toho má P-NP Puzzler důsledky. The New York Times 7. října 2009.
  9. ^ L. Fortnow. Stav problému P Versus NP. Komunikace ACM 9 (2009).
  10. ^ L. Fortnow. Složitost dokonalých nulových znalostí. V S. Micali, editor, Náhodnost a výpočet, svazek 5 Pokroky ve výzkumu výpočetní techniky, strany 327-343. JAI Press, Greenwich, 1989.
  11. ^ L. Fortnow a M. Sipser. Existují interaktivní protokoly pro jazyky co-NP? Dopisy o zpracování informací, 28:249-251, 1988.
  12. ^ C. Lund, L. Fortnow, H. Karloff a N. Nisan. Algebraické metody pro interaktivní kontrolní systémy. Deník ACM, 39(4):859-868, 1992.
  13. ^ A. Shamir. IP = PSPACE. Deník ACM 39(4):869-877, 1992.
  14. ^ L. Babai, L. Fortnow a C. Lund. Nedeterministický exponenciální čas má dva zkušební protokoly. Výpočetní složitost, 1(1):3-40, 1991.
  15. ^ L. Babai, L. Fortnow, L. Levin a M. Szegedy. Kontrola výpočtů v polylogaritmickém čase. v Proceedings of the 23. ACM Symposium on the Theory of Computing, strany 21-31. ACM, New York, 1991.
  16. ^ L. Fortnow a D. Whang. Optimalita a dominance v opakovaných hrách s omezenými hráči. v Proceedings of the 26. ACM Symposium on the Theory of Computing, strany 741-749. ACM, New York, 1994.
  17. ^ Y. Chen, L. Fortnow, N. Lambert, D. Pennock a J. Wortman. Složitost kombinační tvůrci trhu. v Sborník příspěvků z 9. konference ACM o elektronickém obchodu, strany 190-199. ACM, New York, 2008.
  18. ^ Y. Chen, S. Dimitrov, R. Sami, D. Reeves, D. Pennock, R. Hanson, L. Fortnow a R. Gonen. Trhy s predikcí hraní: Rovnovážné strategie s tvůrcem trhu. Algorithmica, 2009.
  19. ^ Fortnow, Lance. The Golden Ticket: P, NP and the Search for the Impossible. Princeton University Press, 2013
  20. ^ Fortnow, Lance. Stav problému P Versus NP. Komunikace ACM, 52 (9): 78-86. Září 2009. Recenze článek
  21. ^ P vs NP. Data Skeptic, 2017

externí odkazy