Umesh Vazirani - Umesh Vazirani

Umesh Vazirani
NárodnostIndicko-americký
Alma materMIT, University of California, Berkeley
OceněníFulkersonova cena (2012)
Vědecká kariéra
PoleKvantový výpočet, Výpočetní složitost
InstituceUniversity of California, Berkeley
TezeNáhodnost, protivníci a výpočet (1986)
Doktorský poradceManuel Blum
Doktorandi
webová stránkawww.cs.berkeley.edu/ ~ vazirani/
Poznámky
Je bratrem Vijay Vazirani.

Umesh Virkumar Vazirani je Indicko-americký akademik, který je profesorem elektrotechniky a informatiky na Roger A. Strauch University of California, Berkeley a ředitel kvantového výpočetního centra Berkeley. Jeho výzkumné zájmy spočívají především v kvantové výpočty. Je také spoluautorem učebnice algoritmů.[1]

Životopis

Vazirani obdržel BS od MIT v roce 1981[2] a získal titul Ph.D. v roce 1986 z UC Berkeley pod dohledem Manuel Blum.[3]

Je bratrem University of California, Irvine profesor Vijay Vazirani.

Výzkum

Vazirani je jedním ze zakladatelů oboru kvantové práce na počítači. Jeho papír z roku 1993, na kterém byl jeho student Ethan Bernstein teorie kvantové složitosti[4] definoval model kvantové Turingovy stroje který byl přístupný analýze založené na složitosti. Tento článek také dal algoritmus pro kvantová Fourierova transformace, který poté použil Peter Shor do jednoho roku oslavil kvantový algoritmus pro factoringová celá čísla.

S Bennettem, Bernsteinem a Brassardem ukázal, že kvantové počítače nedokáží vyřešit problémy s hledáním černé skříňky rychleji než v počtu prvků, které mají být prohledány. Tento výsledek ukazuje, že Groverovo hledání algoritmus je optimální. Ukazuje také, že kvantové počítače nemohou vyřešit NP-kompletní problémy v polynomiálním čase pouze s použitím certifikátoru.[5][6]

Ceny a vyznamenání

V roce 2005 Vazirani i jeho bratr Vijay Vazirani byli uvedeni jako Fellows of the Sdružení pro výpočetní techniku, Umesh za "příspěvky do teoretická informatika a kvantový výpočet "[7] a jeho bratr Vijay za jeho práci na aproximační algoritmy.[8] Vazirani byl oceněn Fulkersonova cena pro rok 2012 za práci na zlepšení aproximačního poměru pro oddělovače grafů a související problémy (společně s Satish Rao a Sanjeev Arora ). V roce 2018 byl zvolen do Národní akademie věd.

Vybrané publikace

  • Mulmuley, Ketan; Vazirani, Umesh V .; Vazirani, Vijay V. (1987), „Matching is as easy as matrix inversion“, Combinatorica, 7 (1): 105–113, doi:10.1007 / BF02579206, PAN  0905157, S2CID  47370049. Předběžná verze tohoto článku byla také publikována ve STOC '87.
  • Bernstein, Ethan; Vazirani, Umesh (1993), „Teorie kvantové složitosti“, Sborník z dvacátého pátého ročníku ACM symposia o teorii práce s počítačem (STOC '93), str. 11–20, CiteSeerX  10.1.1.655.1186, doi:10.1145/167088.167097, ISBN  978-0897915915, S2CID  676378.
  • Kearns, Michael J .; Vazirani, Umesh V. (1994), Úvod do teorie výpočetního učení, MIT Press, ISBN  9780262111935.
  • Bennett, Charles H.; Bernstein, Ethan; Brassard, Gilles; Vazirani, Umesh (1997), „Silné a slabé stránky kvantového výpočtu“, SIAM Journal on Computing, 26 (5): 1510–1523, arXiv:quant-ph / 9701001, doi:10.1137 / S0097539796300933, PAN  1471991, S2CID  13403194.

Reference

  1. ^ Algoritmy: Dasgupta, Papadimitriou, Vazirani
  2. ^ Vazirani, Umesh Virkumar (01.01.1986). Náhodnost, protivníci a výpočet. University of California, Berkeley.
  3. ^ Umesh Virkumar Vazirani na Matematický genealogický projekt.
  4. ^ Bernstein & Vazirani 1993.
  5. ^ Bennett, Charles H .; Bernstein, Ethan; Brassard, Gilles; Vazirani, Umesh (říjen 1997). „Silné a slabé stránky kvantového počítače“. SIAM Journal on Computing. 26 (5): 1510–1523. doi:10.1137 / s0097539796300933. ISSN  0097-5397.
  6. ^ Aaronson, Scott. „Přednáška 23., čtvrtek 13. dubna: BBBV, aplikace Grovera“ (PDF). Citováno 17. listopadu 2020.
  7. ^ Cena ACM Fellows: Umesh Vazirani.
  8. ^ Cena ACM Fellows: Vijay Vazirani.

externí odkazy