Ryan Williams (počítačový vědec) - Ryan Williams (computer scientist) - Wikipedia

Pro ostatní lidi jménem Ryan Williams viz Ryan Williams (rozcestník).
Ryan Williams
Ryan Williams v Dagstuhl 10441.jpg
Williams (listopad 2010)
narozený1979 (věk 40–41)
Národnostamerický
Alma materCornell University
Univerzita Carnegie Mellon
Vědecká kariéra
PoleTeorie výpočetní složitosti, Algoritmy
InstituceUniverzita Carnegie Mellon
Výzkumné centrum IBM Almaden
Stanfordská Univerzita
Doktorský poradceManuel Blum

Richard Ryan Williams, známý jako Ryan Williams (narozen 1979), je americký počítačový vědec pracující v teorie výpočetní složitosti.

Vzdělávání

Williams přijal jeho Bakalářský titul v matematice a informatice od Cornell University v roce 2001[1] a jeho Ph.D v informatice v roce 2007 od Univerzita Carnegie Mellon pod dohledem Manuel Blum.[2] V letech 2010 až 2012 byl členem skupiny Theory Group of Výzkumné centrum IBM Almaden. Od podzimu 2011 do podzimu 2016 působil jako profesor na Stanfordské univerzitě. V lednu 2017 nastoupil na fakultu v MIT [1].

Výzkum

Williams byl členem programového výboru pro Symposium on Theory of Computing v roce 2011 a na různých dalších konferencích. Získal cenu za nejlepší studentský papír Ron V. Book na IEEE Konference o výpočetní složitosti v letech 2005 a 2007,[3] a na nejlepší studentské papírové ceně na Mezinárodní kolokvium o automatech, jazycích a programování v roce 2004 z Evropská asociace pro teoretickou informatiku.[4]

Výsledek Williamsovy třídy složitosti NEXP není obsažen v ACC0 obdržel cenu za nejlepší referát na konferenci o výpočetní složitosti v roce 2011.[5] Teoretik složitosti Scott Aaronson označil výsledek za „jeden z nejpozoruhodnějších desetiletí“.[6]

Williams je také odborníkem na výpočetní složitost k-anonymita.[7]

Osobní život

Ryan je ženatý Virginia Vassilevska Williams, také počítačový vědec.

Vybrané publikace

  • Meyerson, Adam; Williams, Ryan (2004), „O složitosti optima k-anonymita", Sborník z dvacátého třetího sympózia ACM SIGMOD-SIGACT-SIGART o principech databázových systémů (PODS '04), New York, NY, USA: ACM, s. 223–228, doi:10.1145/1055558.1055591, ISBN  978-1581138580
  • Williams, R. (2005), „Lepší časové mezery pro SAT a související problémy“, Konference IEEE o výpočetní složitosti (CCC), s. 40–49
  • Williams, R. (2005), „Nový algoritmus pro optimální 2-omezující spokojenost a jeho důsledky“, Teoretická informatika, 348 (2–3): 357–365, doi:10.1016 / j.tcs.2005.09.023
  • Williams, R. (2008), „Time-Space Lower Bound for Counting NP Solutions Modulo Integers“, Výpočetní složitost, 17 (2): 179–219, doi:10.1007 / s00037-008-0248-r
  • Williams, R. (2011), „Non-Uniform ACC Circuit Lower Bounds“, Konference IEEE o výpočetní složitosti (CCC) (PDF), str. 115–125, CiteSeerX  10.1.1.225.8935, doi:10.1109 / CCC.2011.36, ISBN  978-1-4577-0179-5

Reference

  1. ^ Životopis (PDF), vyvoláno 2017-12-02
  2. ^ Ryan Williams na Matematický genealogický projekt
  3. ^ Sborník z 20. výroční konference IEEE o výpočetní složitosti (CCC'05) San Jose, CA 11. června - 15. června, ISBN  0-7695-2364-1a dvacátá druhá výroční konference IEEE o výpočetní složitosti (CCC'07) San Diego, Kalifornie, 13. června - 16. března, ISBN  0-7695-2780-9.
  4. ^ „Nejlepší studentský papír ICALP“. Evropská asociace pro teoretickou informatiku (EATCS).
  5. ^ Program pro CCC2011 na http://computationalcomplexity.org/
  6. ^ Aaronson, Scott (8. listopadu 2010), „Stav dolních mezí okruhu nyní o něco méně ponižující“, Recenze technologie MIT.
  7. ^ Meyerson & Williams (2004).

externí odkazy