William Gasarch - William Gasarch

William Ian Gasarch
narozený1959 (věk 60–61 let)
NárodnostSpojené státy
Alma materUniverzita Stony Brook
Harvardská Univerzita
Známý jakoTeorie výpočetní složitosti, Teorie vypočítatelnosti, Teorie výpočetního učení, Ramseyova teorie
Vědecká kariéra
PolePočítačová věda
InstituceUniversity of Maryland, College Park
Doktorský poradceHarry R. Lewis
webová stránkawww.cs.umd.edu/ ~ gasarch
http://blog.computationalcomplexity.org/

William Ian Gasarch (narozen 1959[1]) je počítačový vědec známý svou prací v teorie výpočetní složitosti, teorie vypočítatelnosti, teorie výpočetního učení, a Ramseyova teorie. V současné době je profesorem na University of Maryland Katedra informatiky s přidruženým jmenováním do matematiky.

Od roku 2015 dohlížel na více než 40 středoškolských studentů na výzkumné projekty,[Citace je zapotřebí ] počítaje v to Jacob Lurie. Spolupracoval na blogu o výpočetní složitosti s Lance Fortnow od roku 2007. Byl redaktorem recenze knihy pro ACM SIGACT ZPRÁVY z let 1997–2015, poté rezignoval a předal práci Fredovi Greenovi, profesorovi výpočetní techniky na Clarkové univerzitě.

Vzdělávání

Gasarch získal doktorát z informatiky od Harvard v roce 1985, doporučeno Harry R. Lewis. Jeho práce měla název Rekurzivně-teoretické techniky v teorii složitosti a kombinatorice.[2] Na podzim roku 1985 byl přijat na místo profesora na univerzitě v Marylandu. Byl povýšen na docenta s funkcí v roce 1991 a na řádného profesora v roce 1998.[Citace je zapotřebí ]

Práce

Gasarch spolu s Richardem Beigelem založil pole Bounded Queries v teorii rekurze[3] a napsal mnoho článků v této oblasti uzavřených knihou na toto téma spoluautorem s Georgem Martinem Omezené dotazy v teorii rekurze.[4] Vydal knihy jako např Problémy s bodem,[5] kniha se širokým pohledem na matematiku a teoretickou informatiku, se kterou byl spoluautorem Clyde Kruskal a zahrnuje díla jiných profesorů, jako např David Eppstein.[6] Spoluzaložil také podpole rekurzně-teoretické indukční inference pojmenované Učení pomocí dotazů[7] s Carl Smith. V poslední době se více věnuje kombinatorice, zejména Ramseyově teorii.[8][9][10] Napsal dva průzkumy toho, co si teoretici myslí o P vs NP problém.[11][12]

Blog

Lance Fortnow začal psát blog o teoretické počítačové vědě s důrazem na teorii složitosti v roce 2003.[13] Gasarch byl častým hostujícím bloggerem až do roku 2007, kdy se stal oficiálním spolublogerem.

Reference

  1. ^ „Stále obsadit Dagstuhl“. Výpočetní složitost Weblog. Lance Fortnow a William Gasarch. Citováno 27. září 2018.
  2. ^ William Gasarch na Matematický genealogický projekt
  3. ^ http://www.cs.umd.edu/~gasarch/papers/gems.pdf Drahokamy v oblasti ohraničených dotazů od Williama Gasarcha, 2003
  4. ^ https://www.springer.com/us/book/9780817639662 Ohraničené dotazy v teorii rekurze (s Georgem Martinem), Birkhauser, 1999
  5. ^ https://www.worldscientific.com/worldscibooks/10.1142/11261 Problémy s bodem zkoumajícím matematiku a informatiku, 2019
  6. ^ https://www.worldscientific.com/doi/abs/10.1142/9789813279735_0014 Kapitola 14: Je tento problém příliš obtížný pro matematické soutěže na střední škole ?, 2019
  7. ^ http://www.cs.umd.edu/~gasarch/papers/lvqsur.pdf Průzkum indukčního závěru s důrazem na dotazy, Gasarch a Smith, 1997
  8. ^ Gasarch, William; Haeupler, Bernhard (2011). „Dolní hranice na číslech van der Waerden: Randomized- a Deterministic-Constructive“. Electronic Journal of Combinatorics. 18 (64). arXiv:1005.3749. doi:10.37236/551.
  9. ^ Gasarch, William; Haeupler, Bernhard (2010). "Obdélníkové vybarvení mřížek". arXiv:1005.3750 [math.CO ].
  10. ^ Gasarch, William; Haeupler, Bernhard (2011). „Proving programs terminate using well orderings, Ramsey Theory, and Matrices“. arXiv:1108.3347 [math.CO ].
  11. ^ http://www.cs.umd.edu/~gasarch/papers/poll.pdf Anketa P =? NP, William Gasarch, hostující sloupek ve SIGACT NEWS Sloupec teorie složitosti 36, 2002
  12. ^ http://www.cs.umd.edu/~gasarch/papers/poll2012.pdf The Second P =? NP Poll, William Gasarch, Guest Column in SIGACT NEWS Complexity TEE Column 74, 2012
  13. ^ http://blog.computationalcomplexity.org/ Výpočetní složitost Weblog

externí odkazy