Education
Vazirani received a Bachelor of Science from Massachusetts Institute of Technology in 1981 and received his Doctor of Philosophy in 1986 from University of California Berkeley under the supervision of Manuel Blum.
Vazirani received a Bachelor of Science from Massachusetts Institute of Technology in 1981 and received his Doctor of Philosophy in 1986 from University of California Berkeley under the supervision of Manuel Blum.
His research interests lie primarily in quantum computing. He is also the author of a textbook on algorithms. He is the brother of Georgia Technical College of Computing professor Vijay Vazirani.
Vazirani is one of the founders of the field of quantum computing.
His 1993 paper with his student Ethan Bernstein on quantum complexity theory defined a model of quantum Turing machines which was amenable to complexity based analysis. This paper also gave an algorithm for the quantum Fourier transform, which was then used by Peter Shor within a year in his celebrated quantum algorithm for factoring integers.
In 2005 both Vazirani and his brother were inducted as Fellows of the Association for Computing Machinery, Umesh for “contributions to theoretical computer science and quantum computation” and his brother Vijay for his work on approximation algorithms. Vazirani was awarded the Fulkerson Prize for 2012 for his work on improving the approximation ratio for graph separators and related problems (jointly with Satish Rao and Sanjeev Arora).
Selected publications 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, MR 905157. A preliminary version of this paper was also published in STOC '87. Bernstein, Ethan.
Vazirani, Umesh (1993), "Quantum complexity theory", Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC '93), pp. 11–20, doi:10.1145/167088.167097 . Kearns, Michael J. Vazirani, Umesh V. (1994), An Introduction to Computational Learning Theory, MIT Press, . Bennett, Charles H.
Bernstein, Ethan
Brassard, Gilles. Vazirani, Umesh (1997), "Strengths and weaknesses of quantum computing", SIAM Journal on Computing 26 (5): 1510–1523, arXiv:quant-ph/9701001, doi:10.1137/S0097539796300933, MR 1471991.
