Vijay Vazirani

Vijay Vazirani
Vijay Vazirani
	vid UC Irvine , 2021
Född	1957; Indien
Nationalitet	amerikansk
Alma mater	; ; MIT (bachelor) University of California, Berkeley (PhD) Harvard University (PostDoc)
Känd för	Valiant–Vazirani-satsen , Isolationslemma
Släktingar	Umesh Vazirani (bror)
Utmärkelser	ACM-stipendiat; Guggenheim Fellowship; John von Neumann teoripris;
	Vetenskaplig karriär
Fält	algoritmer , beräkningskomplexitetsteori , algoritmisk spelteori .
institutioner	Georgia Institute of Technology; Indian Institute of Technology, Delhi; University of California, Irvine;
Avhandling	Maximum Matchings without Blossoms (1985)
Doktorandrådgivare	Manuel Blum
Doktorander	Naveen Garg; Samir Khuller;
Hemsida	www .ics .uci .edu /~vazirani

Vijay Virkumar Vazirani ( hindi : विजय वीरकुमार वज़ीरानी ; f. 1957) är en professor i indisk datavetenskap vid Donald-amerikanska datavetenskapsskola I, USA, i datavetenskap vid Donald, USA. vinstockar .

Utbildning och karriär

Vazirani tog först huvudämne i elektroteknik vid Indian Institute of Technology, Delhi, men under sitt andra år gick han över till MIT och tog sin kandidatexamen i datavetenskap från MIT 1979 och sin doktorsexamen . från University of California, Berkeley 1983. Hans avhandling, Maximum Matchings without Blossoms , övervakades av Manuel Blum . Efter postdoktoral forskning med Michael O. Rabin och Leslie Valiant vid Harvard University började han på fakulteten vid Cornell University 1984. Han flyttade till IIT Delhi som professor 1990 och flyttade igen till Georgia Institute of Technology 1995. Han var också McKay gästprofessor vid University of California, Berkeley , och en framstående SISL-besökare vid Social and Information Sciences Laboratory vid California Institute of Technology . 2017 flyttade han till University of California, Irvine som framstående professor.

Forskning

Vaziranis forskarkarriär har varit centrerad kring design av algoritmer , tillsammans med arbete med beräkningskomplexitetsteori , kryptografi och algoritmisk spelteori .

Under 1980-talet gjorde han avgörande bidrag till det klassiska maximala matchningsproblemet , och några viktiga bidrag till beräkningskomplexitetsteorin , t.ex. isoleringslemmat , Valiant -Vazirani-teoremet och ekvivalensen mellan slumpmässig generering och ungefärlig räkning. Under 1990-talet arbetade han mestadels med approximationsalgoritmer , och kämpade för primal-dual-schemat, som han tillämpade på problem som uppstod i nätverksdesign, lokalisering av anläggningar och webbcache, och klustring. I juli 2001 publicerade han vad som allmänt anses vara den definitiva boken om approximationsalgoritmer (Springer-Verlag, Berlin). Sedan 2002 har han stått i spetsen för arbetet med att förstå beräkningsbarheten av marknadsjämvikter, med ett omfattande arbete kring ämnet.

Hans forskningsresultat inkluderar också att bevisa, tillsammans med Leslie Valiant , att om UNIQUE-SAT är i P , så är NP = RP ( Valiant–Vaziranis sats ), och att 1980, tillsammans med Silvio Micali , erhålla en algoritm för att hitta maximala matchningar i allmänhet grafer; den senare är fortfarande den mest effektiva kända algoritmen för problemet. Med Mehta, Saberi och Umesh Vazirani visade han 2007 hur man formulerade problemet med att välja annonser för AdWords som ett onlinematchningsproblem och hittade en lösning på detta problem med optimal konkurrensförhållande .

Pris och ära

År 2005 valdes både Vazirani och hans bror Umesh Vazirani (också en teoretisk datavetare vid University of California, Berkeley ) in som Fellows av Association for Computing Machinery . 2011 tilldelades han ett Guggenheim Fellowship .

År 2022 fick Vazirani John von Neumann Theory Prize för "grundläggande och hållbara bidrag till utformningen av algoritmer, inklusive approximationsalgoritmer, beräkningskomplexitetsteori och algoritmisk spelteori, centrala för operationsforskning och managementvetenskap".

Se även

Lista över indiska matematiker

^ Deutsche Nationalbibliothek
^ Vijay Vazirani vid Mathematics Genealogy Project
^ Tre av hans artiklar i ämnet från den tidsperioden har över 100 citat vardera, enligt Google-forskare: Micali, S. ; Vazirani, VV (1980), "En ${\displaystyle \scriptstyle O({\sqrt {|V|}}\cdot |E|)}-$ algoritm för att hitta maximal matchning i allmänna grafer ", Proc. 21:a IEEE Symp. Foundations of Computer Science , 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), "En optimal algoritm för on-line bipartite matchning", Proc 22nd ACM Symp. Theory of Computing , s. 352–358, doi : 10.1145/100216.100262 , ISBN 0-89791-361-2 , S2CID 822904 .
^ Jerrum, Mark R.; Valiant, Leslie G.; Vazirani, Vijay V. (1986), "Slumpmässig generering av kombinatoriska strukturer från en enhetlig distribution", Theoretical Computer Science , 43 (2–3): 169–188, doi : 10.1016/0304-3975(86)90174-X , MR 0855970 . Se Bubley, Russ (2001), Randomized algorithms: approximation, generation, and counting , CPHC/BCS Distinguished Dissertations, Springer-Verlag, sid. 120, doi : 10.1007/978-1-4471-0695-1 , ISBN 1-85233-325-1 , MR 1986183 ; Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective , Cambridge University Press, sid. 229, ISBN 9781139472746 .
^ Jain, Kamal; Vazirani, Vijay V. (2001), "Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation", Journal of the ACM , 48 (2): 274–296, doi : 10.1145/ 375827.375845 , MR 1868717 , S2CID 2353092 . Se Williamson, David P.; Shmoys, David B. (2011), The Design of Approximation Algorithms , Cambridge University Press, sid. 191, ISBN 9781139498173
^ Mehta, Aranyak; Saberi, Amin; Vazirani, Umesh; Vazirani, Vijay (2007), "AdWords and generalized online matching", Journal of the ACM , 54 (5): Art. 22, 19, doi : 10.1145/1284320.1284321 , MR 2359264 , S2CID 8481313
^ ACM Fellows Award: Umesh Vazirani Arkiverad 14 december 2007, på Wayback Machine .
^ ACM Fellows Award: Vijay Vazirani Arkiverad 14 december 2007, på Wayback Machine .
^ "2022 INFORMERAR årsmötesutmärkelsehallen" . 2022 INFORMERAR Årsmöte . Hämtad 2022-11-08 .

externa länkar

Hemsida på UC Irvine
Vijay Vazirani -publikationer indexerade av Google Scholar

[1] Deutsche Nationalbibliothek

[2] Vijay Vazirani vid Mathematics Genealogy Project

[3] Tre av hans artiklar i ämnet från den tidsperioden har över 100 citat vardera, enligt Google-forskare: Micali, S. ; Vazirani, VV (1980), "En ${\displaystyle \scriptstyle O({\sqrt {|V|}}\cdot |E|)}-$ algoritm för att hitta maximal matchning i allmänna grafer ", Proc. 21:a IEEE Symp. Foundations of Computer Science , 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), "En optimal algoritm för on-line bipartite matchning", Proc 22nd ACM Symp. Theory of Computing , s. 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), "Slumpmässig generering av kombinatoriska strukturer från en enhetlig distribution", Theoretical Computer Science , 43 (2–3): 169–188, doi : 10.1016/0304-3975(86)90174-X , MR 0855970 . Se Bubley, Russ (2001), Randomized algorithms: approximation, generation, and counting , CPHC/BCS Distinguished Dissertations, Springer-Verlag, sid. 120, doi : 10.1007/978-1-4471-0695-1 , ISBN 1-85233-325-1 , MR 1986183 ; Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective , Cambridge University Press, sid. 229, ISBN 9781139472746 .

[5] Jain, Kamal; Vazirani, Vijay V. (2001), "Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation", Journal of the ACM , 48 (2): 274–296, doi : 10.1145/ 375827.375845 , MR 1868717 , S2CID 2353092 . Se Williamson, David P.; Shmoys, David B. (2011), The Design of Approximation Algorithms , Cambridge University Press, sid. 191, ISBN 9781139498173

[6] Mehta, Aranyak; Saberi, Amin; Vazirani, Umesh; Vazirani, Vijay (2007), "AdWords and generalized online matching", Journal of the ACM , 54 (5): Art. 22, 19, doi : 10.1145/1284320.1284321 , MR 2359264 , S2CID 8481313

[7] ACM Fellows Award: Umesh Vazirani Arkiverad 14 december 2007, på Wayback Machine .

[8] ACM Fellows Award: Vijay Vazirani Arkiverad 14 december 2007, på Wayback Machine .

[9] "2022 INFORMERAR årsmötesutmärkelsehallen" . 2022 INFORMERAR Årsmöte . Hämtad 2022-11-08 .

Myndighetskontroll
Internationell	ISNI VIAF WorldCat-identiteter
Nationell	Norge Frankrike BnF-data Tyskland Israel Förenta staterna Lettland Japan Tjeckien Nederländerna Polen
Akademiker	Föreningen för Datormaskiner DBLP Google Scholar MathSciNet Matematik släktforskningsprojekt zbMATH
Övrig	IdRef

Vijay Vazirani
vid UC Irvine , 2021
Född	1957 Indien
Nationalitet	amerikansk
Alma mater	MIT (bachelor) University of California, Berkeley (PhD) Harvard University (PostDoc)
Känd för	Valiant–Vazirani-satsen , Isolationslemma
Släktingar	Umesh Vazirani (bror)
Utmärkelser	ACM-stipendiat Guggenheim Fellowship John von Neumann teoripris
Vetenskaplig karriär
Fält	algoritmer , beräkningskomplexitetsteori , algoritmisk spelteori .
institutioner	Georgia Institute of Technology Indian Institute of Technology, Delhi University of California, Irvine
Avhandling	Maximum Matchings without Blossoms (1985)
Doktorandrådgivare	Manuel Blum
Doktorander	Naveen Garg Samir Khuller

Hemsida	www .ics .uci .edu /~vazirani