Umesh Vazirani

Académico indio-americano

Umesh Vazirani
Nacionalidad	Indio-americano
alma mater	MIT , Universidad de California, Berkeley
Conocido por	Algoritmo de Bernstein-Vazirani
Premios	Premio Fulkerson (2012)
Carrera científica
Los campos	Computación cuántica , complejidad computacional
Instituciones	Universidad de California, Berkeley
Tesis	Aleatoriedad, adversarios y computación  (1986)
Asesor de doctorado	Manuel Blum
Estudiantes de doctorado	Scott Aaronson Andris Ambainis Sanjeev Arora Urmila Mahadev Madhu Sudán David Zuckerman
Sitio web	www .cs .berkeley .edu / ~ vazirani /
Notas
Es el hermano de Vijay Vazirani .

Umesh Virkumar Vazirani es un académico indio-americano que es profesor Roger A. Strauch de Ingeniería Eléctrica y Ciencias de la Computación en la Universidad de California, Berkeley , y director del Centro de Computación Cuántica de Berkeley. Sus intereses de investigación se encuentran principalmente en la computación cuántica . También es coautor de un libro de texto sobre algoritmos. ^[1]

Biografía

Vazirani recibió una licenciatura del MIT en 1981 ^[2] y recibió su Ph.D. en 1986 de UC Berkeley bajo la supervisión de Manuel Blum . ^[3]

Es hermano del profesor Vijay Vazirani de la Universidad de California en Irvine .

Investigar

Vazirani es uno de los fundadores del campo de la computación cuántica. Su artículo de 1993 con su alumno Ethan Bernstein sobre la teoría de la complejidad cuántica ^[4] definió un modelo de máquinas cuánticas de Turing que era susceptible de análisis basado en la complejidad. Este artículo también proporcionó un algoritmo para la transformada cuántica de Fourier , que luego fue utilizado por Peter Shor dentro de un año en su célebre algoritmo cuántico para factorizar enteros .

Con Charles Bennett , Ethan Bernstein y Gilles Brassard , demostró que las computadoras cuánticas no pueden resolver los problemas de búsqueda de caja negra más rápido que en la cantidad de elementos a buscar. Este resultado muestra que el algoritmo de búsqueda de Grover es óptimo. También muestra que las computadoras cuánticas no pueden resolver problemas NP-completos en tiempo polinomial usando solo el certificador. ^{[5] [6] [ dudoso - discutir ]}${\displaystyle O({\sqrt {N}})}$

Premios y honores

En 2005, tanto Vazirani como su hermano Vijay Vazirani fueron admitidos como Fellows de la Association for Computing Machinery , Umesh por "contribuciones a la informática teórica y la computación cuántica " ^[7] y su hermano Vijay por su trabajo en algoritmos de aproximación . ^[8] Vazirani fue galardonado con el Premio Fulkerson de 2012 por su trabajo en la mejora de la relación de aproximación para separadores de gráficos y problemas relacionados (junto con Satish Rao y Sanjeev Arora ). En 2018, fue elegido miembro de la Academia Nacional de Ciencias .

Publicaciones Seleccionadas

• Mulmuley, Ketan; Vazirani, Umesh V .; Vazirani, Vijay V. (1987), "Emparejar es tan fácil como la inversión de matrices", Combinatorica , 7 (1): 105-113, doi : 10.1007 / BF02579206 , MR  0905157 , S2CID  47370049. También se publicó una versión preliminar de este artículo en STOC '87.
• Bernstein, Ethan; Vazirani, Umesh (1993), "Teoría de la complejidad cuántica", Actas del Vigésimo Quinto Simposio Anual de ACM sobre Teoría de la Computación (STOC '93) , págs. 11-20, CiteSeerX  10.1.1.655.1186 , doi : 10.1145 / 167088.167097 , ISBN 978-0897915915, S2CID  676378.
• Kearns, Michael J .; Vazirani, Umesh V. (1994), Introducción a la teoría del aprendizaje computacional , MIT Press, ISBN 9780262111935.
• Bennett, Charles H .; Bernstein, Ethan; Brassard, Gilles ; Vazirani, Umesh (1997), "Fortalezas y debilidades de la computación cuántica", SIAM Journal on Computing , 26 (5): 1510-1523, arXiv : quant-ph / 9701001 , Bibcode : 1997quant.ph..1001B , doi : 10.1137 / S0097539796300933 , MR  1.471.991 , S2CID  13403194.

Referencias

1. Algoritmos: Dasgupta, Papadimitriou, Vazirani
2. Vazirani, Umesh Virkumar (1 de enero de 1986). Aleatoriedad, adversarios y computación . Universidad de California, Berkeley.
3. Umesh Virkumar Vazirani en el Proyecto de genealogía de las matemáticas .
4. Bernstein y Vazirani 1993 .
5. Bennett, Charles H .; Bernstein, Ethan; Brassard, Gilles; Vazirani, Umesh (octubre de 1997). "Fortalezas y debilidades de la Computación Cuántica" . Revista SIAM de Computación . 26 (5): 1510-1523. arXiv : quant-ph / 9701001 . Código bibliográfico : 1997quant.ph..1001B . doi : 10.1137 / s0097539796300933 . ISSN 0097-5397 . S2CID 13403194 .  
6. Aaronson, Scott. "Conferencia 23, jueves 13 de abril: BBBV, Aplicaciones de Grover" (PDF) . Consultado el 17 de noviembre de 2020 .
7. Premio ACM Fellows: Umesh Vazirani .
8. Premio ACM Fellows: Vijay Vazirani .

enlaces externos

• Página web en UC Berkeley