Vijay Virkumar Vazirani ( hindi : विजय वीरकुमार वज़ीरानी ; n. 1957 [1] ) es un distinguido profesor indio americano de informática en la Escuela de Información y Ciencias de la Computación Donald Bren de la Universidad de California, Irvine .
Vazirani se especializó por primera vez en ingeniería eléctrica en el Instituto Indio de Tecnología de Delhi, pero en su segundo año se transfirió al MIT y recibió su licenciatura en ciencias de la computación del MIT en 1979 y su doctorado. de la Universidad de California, Berkeley en 1983. Su tesis, Máximos emparejamientos sin flores , fue supervisada por Manuel Blum . [2] Después de una investigación postdoctoral con Michael O. Rabin y Leslie Valiant en la Universidad de Harvard , se unió a la facultad de la Universidad de Cornell en 1984. Se mudó al IIT Delhi como profesor titular en 1990 y se mudó nuevamente al Instituto de Tecnología de Georgia. en 1995. También fue profesor visitante McKay en la Universidad de California, Berkeley , y visitante distinguido de SISL en el Laboratorio de Ciencias Sociales y de la Información del Instituto de Tecnología de California . En 2017 se trasladó a la Universidad de California, Irvine, como profesor distinguido.
La carrera investigadora de Vazirani se ha centrado en el diseño de algoritmos , junto con trabajos en teoría de la complejidad computacional , criptografía y teoría algorítmica de juegos .
Durante la década de 1980, hizo contribuciones fundamentales al problema clásico de coincidencia máxima [3] y algunas contribuciones clave a la teoría de la complejidad computacional , por ejemplo, el lema de aislamiento , el teorema de Valiant-Vazirani y la equivalencia entre generación aleatoria y conteo aproximado. [4] Durante la década de 1990 trabajó principalmente en algoritmos de aproximación , defendiendo el esquema dual primario, que aplicó a problemas que surgían en el diseño de redes, ubicación de instalaciones [5] y almacenamiento en caché web y agrupación en clústeres. En julio de 2001 publicó lo que se considera ampliamente como el libro definitivo sobre algoritmos de aproximación (Springer-Verlag, Berlín). Desde 2002, ha estado a la vanguardia del esfuerzo por comprender la computabilidad de los equilibrios de mercado, con un extenso trabajo sobre el tema.
Los resultados de su investigación también incluyen demostrar, junto con Leslie Valiant , que si UNIQUE-SAT está en P , entonces NP = RP ( teorema de Valiant-Vazirani ), y obtener en 1980, junto con Silvio Micali , un algoritmo para encontrar coincidencias máximas en general. gráficos; este último sigue siendo el algoritmo conocido más eficiente para el problema. Con Mehta, Saberi y Umesh Vazirani, mostró en 2007 cómo formular el problema de elegir anuncios para AdWords como un problema de concordancia en línea , y encontró una solución a este problema con una relación competitiva óptima . [6]
En 2005, tanto Vazirani como su hermano Umesh Vazirani (también científico informático teórico de la Universidad de California, Berkeley ) fueron admitidos como miembros de la Association for Computing Machinery . [7] [8] En 2011, recibió una beca Guggenheim .
En 2022, Vazirani recibió el Premio de Teoría John von Neumann por "contribuciones fundamentales y sostenidas al diseño de algoritmos, incluidos algoritmos de aproximación, teoría de la complejidad computacional y teoría algorítmica de juegos, fundamentales para la investigación de operaciones y las ciencias de la gestión". [9]