stringtranslate.com

Vijay Vazirani

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 .

Educación y carrera

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.

Investigación

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]

Premios y honores

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]

Ver también

Referencias

  1. ^ Biblioteca Nacional Alemana
  2. ^ Vijay Vazirani en el Proyecto de Genealogía de Matemáticas
  3. ^ Tres de sus artículos sobre el tema de ese período tienen más de 100 citas cada uno, según Google Scholar: Micali, S .; Vazirani, VV (1980), "Un algoritmo para encontrar la máxima coincidencia en gráficos generales", Proc. 21º Simposio IEEE. Fundamentos de la informática , págs. 17–27, doi :10.1109/SFCS.1980.12, S2CID  27467816; Mulmuley, Ketan ; Vazirani, Umesh V .; Vazirani, Vijay V. (1987), "La comparación es tan fácil como la inversión de matrices", Combinatorica , 7 (1): 105–113, doi :10.1007/BF02579206, S2CID  47370049; Karp, Richard M .; Vazirani, Umesh V.; Vazirani, Vijay V. (1990), "Un algoritmo óptimo para la coincidencia bipartita en línea", Proc 22nd ACM Symp. Teoría de la Computación , págs. 352–358, doi :10.1145/100216.100262, ISBN 0-89791-361-2, S2CID  822904.
  4. ^ Jerrum, Mark R.; Valiente, Leslie G.; Vazirani, Vijay V. (1986), "Generación aleatoria de estructuras combinatorias a partir de una distribución uniforme", Ciencias de la Computación Teórica , 43 (2–3): 169–188, doi : 10.1016/0304-3975(86)90174-X , Señor  0855970. Véase Bubley, Russ (2001), Algoritmos aleatorios: aproximación, generación y conteo, Disertaciones distinguidas de CPHC/BCS, Springer-Verlag, pág. 120, doi :10.1007/978-1-4471-0695-1, ISBN 1-85233-325-1, SEÑOR  1986183, S2CID  266744010; Goldreich, Oded (2008), Complejidad computacional: una perspectiva conceptual, Cambridge University Press, pág. 229, ISBN 9781139472746.
  5. ^ Jainista, Kamal; Vazirani, Vijay V. (2001), "Algoritmos de aproximación para la ubicación de instalaciones métricas y problemas de k-mediana utilizando el esquema dual primario y la relajación lagrangiana", Journal of the ACM , 48 (2): 274–296, doi :10.1145/ 375827.375845, SEÑOR  1868717, S2CID  2353092. Véase Williamson, David P.; Shmoys, David B. (2011), El diseño de algoritmos de aproximación, Cambridge University Press, pág. 191, ISBN 9781139498173
  6. ^ Mehta, Aranyak; Saberi, Amin; Vazirani, Umesh; Vazirani, Vijay (2007), "AdWords y concordancia en línea generalizada", Journal of the ACM , 54 (5): art. 22, 19, doi :10.1145/1284320.1284321, SEÑOR  2359264, S2CID  8481313
  7. ^ Premio ACM Fellows: Umesh Vazirani Archivado el 14 de diciembre de 2007 en Wayback Machine .
  8. ^ Premio ACM Fellows: Vijay Vazirani Archivado el 14 de diciembre de 2007 en Wayback Machine .
  9. ^ "Sala de Premios de la Reunión Anual INFORMS 2022". 2022 INFORMA Reunión Anual . 5 de octubre de 2022 . Consultado el 8 de noviembre de 2022 .

enlaces externos