Vijay Vazirani - Vijay Vazirani

Vijay Vazirani
Vijay Vazirani.jpg
Vijay Vazirani v roce 2010 na návštěvě University of California, Berkeley.
narozený1957
Národnostamerický
Alma materMIT (Bakalářský titul)
University of California, Berkeley (PhD)
Ocenění
Vědecká kariéra
Polealgoritmy, teorie výpočetní složitosti, teorie algoritmických her.
Instituce
Doktorský poradceManuel Blum
Doktorandi

Vijay Virkumar Vazirani (hindština: विजय वीरकुमार वज़ीरानी; b. 1957[1]) je Indický Američan významný profesor výpočetní techniky v Donald Bren School of Information and Computer Sciences na University of California, Irvine.

Vzdělání a kariéra

Vazirani přijal jeho Bakalářský titul z MIT v roce 1979 a jeho Ph.D. z University of California, Berkeley v roce 1983. Jeho disertační práce, Maximální počet zápasů bez květů, byl pod dohledem Manuel Blum.[2]Po postdoktorandském výzkumu s Michael O. Rabin a Leslie Valiant na Harvardská Univerzita, nastoupil na fakultu v Cornell University v roce 1984. Přestěhoval se do Indický technologický institut, Dillí jako řádný profesor v roce 1990 a znovu se přestěhoval do Gruzínský technologický institut v roce 1995. Byl také hostujícím profesorem McKay na University of California, Berkeley a významný návštěvník SISL v Laboratoři sociálních a informačních věd v Kalifornský technologický institut. V roce 2017 se přestěhoval do University of California, Irvine jako význačný profesor.

Výzkum

Vaziraniho výzkumná kariéra byla soustředěna kolem designu algoritmy, společně s prací na teorie výpočetní složitosti, kryptografie, a teorie algoritmických her.

Během osmdesátých let významně přispěl ke klasice maximální shoda problém,[3] a některé klíčové příspěvky k teorie výpočetní složitosti, např izolační lemma, Věta Valiant-Vazirani a ekvivalence mezi náhodným generováním a přibližným počítáním.[4] V 90. letech pracoval převážně na aproximační algoritmy, prosazující primární-duální schéma, které aplikoval na problémy vznikající při návrhu sítě, umístění zařízení[5] a ukládání do mezipaměti webu a shlukování. V červenci 2001 vydal něco, co je obecně považováno za definitivní knihu aproximační algoritmy (Springer-Verlag, Berlín). Od roku 2002 stojí v popředí snahy o pochopení vypočítatelnosti tržních rovnováh s rozsáhlou prací na tomto tématu.

Mezi jeho výsledky výzkumu patří také dokazování Leslie Valiant, to když JEDINEČNÝ-SAT je v P, pak NP = RP (Věta Valiant – Vazirani ), a získání v roce 1980, spolu s Silvio Micali, algoritmus pro nalezení maximálního shody v obecných grafech; druhý je stále nejúčinnějším známým algoritmem problému. S Mehtou, Saberim a Umeshem Vaziranim v roce 2007 ukázal, jak formulovat problém výběru reklam pro AdWords jako online odpovídající problém, a našel řešení tohoto problému s optimální konkurenční poměr.[6]

Ceny a vyznamenání

V roce 2005 Vazirani i jeho bratr Umesh Vazirani (také teoretický počítačový vědec na University of California, Berkeley ) byli uvedeni jako Fellows of the Sdružení pro výpočetní techniku.[7][8]V roce 2011 mu byla udělena a Guggenheimovo společenství.

Viz také

Reference

  1. ^ Deutsche Nationalbibliothek
  2. ^ Vijay Vazirani na Matematický genealogický projekt
  3. ^ Tři z jeho prací na toto téma z tohoto časového období mají podle vědce Google každý přes 100 citací: Micali, S.; Vazirani, V. V. (1980), „An algoritmus pro nalezení maximální shody v obecných grafech ", Proc. 21. IEEE Symp. Základy informatiky, s. 17–27, doi:10.1109 / SFCS.1980.12, S2CID  27467816; 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, S2CID  47370049; Karp, Richard M.; Vazirani, Umesh V .; Vazirani, Vijay V. (1990), „Optimální algoritmus pro online bipartitní párování“, Proc 22. ACM Symp. Teorie výpočtu, str. 352–358, doi:10.1145/100216.100262, ISBN  0-89791-361-2, S2CID  822904.
  4. ^ Jerrum, Mark R .; Valiant, Leslie G .; Vazirani, Vijay V. (1986), „Náhodné generování kombinatorických struktur z jednotného rozdělení“, Teoretická informatika, 43 (2–3): 169–188, doi:10.1016 / 0304-3975 (86) 90174-X, PAN  0855970. Vidět Bubley, Russ (2001), Randomizované algoritmy: aproximace, generování a počítání, Distribuované disertační práce CPHC / BCS, Springer-Verlag, str. 120, doi:10.1007/978-1-4471-0695-1, ISBN  1-85233-325-1, PAN  1986183; Goldreich, Oded (2008), Výpočetní složitost: koncepční perspektiva, Cambridge University Press, str. 229, ISBN  9781139472746.
  5. ^ Jain, Kamal; Vazirani, Vijay V. (2001), „Aproximační algoritmy pro lokalizaci metrických zařízení a k-mediánové problémy s využitím schématu primal-dual a Lagrangeova relaxace“, Deník ACM, 48 (2): 274–296, doi:10.1145/375827.375845, PAN  1868717, S2CID  2353092. Vidět Williamson, David P .; Shmoys, David B. (2011), Návrh aproximačních algoritmů, Cambridge University Press, str. 191, ISBN  9781139498173
  6. ^ Mehta, Aranyak; Saberi, Amin; Vazirani, Umesh; Vazirani, Vijay (2007), „AdWords and generalized online matching“, Deník ACM, 54 (5): Čl. 22, 19, doi:10.1145/1284320.1284321, PAN  2359264, S2CID  8481313
  7. ^ Cena ACM Fellows: Umesh Vazirani Archivováno 14. Prosince 2007 v Wayback Machine.
  8. ^ Cena ACM Fellows: Vijay Vazirani Archivováno 14. Prosince 2007 v Wayback Machine.

externí odkazy