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ó primero en ingeniería eléctrica en el Instituto Indio de Tecnología de Delhi, pero en su segundo año se trasladó al MIT y recibió su licenciatura en informática del MIT en 1979 y su doctorado de la Universidad de California, Berkeley en 1983. Su disertación, Maximum Matchings without Blossoms , fue supervisada por Manuel Blum . [2] Después de la 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 trasladó al IIT Delhi como profesor titular en 1990, y se trasladó de nuevo 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 de investigación de Vazirani se ha centrado en el diseño de algoritmos , junto con el trabajo en la teoría de la complejidad computacional , la criptografía y la teoría de juegos algorítmicos .
Durante la década de 1980, hizo contribuciones seminales al problema clásico de emparejamiento máximo , [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 primal-dual, que aplicó a problemas que surgieron en el diseño de redes, ubicación de instalaciones [5] y almacenamiento en caché web, y agrupamiento. 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 cuerpo de trabajo sobre el tema.
Sus resultados de investigación también incluyen probar, 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 grafos generales; 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 elección de anuncios para AdWords como un problema de coincidencia 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 incluidos como miembros de la Association for Computing Machinery . [7] [8] En 2011, se le concedió 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 los algoritmos de aproximación, la teoría de la complejidad computacional y la teoría de juegos algorítmicos, fundamentales para la investigación de operaciones y las ciencias de la gestión". [9]
