Umesh Vazirani | |
|---|---|
| Nationality | Indian–American |
| Alma mater | MIT, University of California, Berkeley |
| Known for | Bernstein-Vazirani algorithm |
| Relatives | Vijay Vazirani (brother) |
| Awards | Fulkerson Prize (2012) |
| Scientific career | |
| Fields | Quantum computation, Computational complexity |
| Institutions | University of California, Berkeley |
| Thesis | Randomness, Adversaries and Computation (1986) |
| Doctoral advisor | Manuel Blum |
| Doctoral students | |
| Website |
www |
Umesh Virkumar Vazirani is an Indian–American academic who is the Roger A. Strauch Professor of Electrical Engineering and Computer Science at the University of California, Berkeley, and the director of the Berkeley Quantum Computation Center. His research interests lie primarily in quantum computing. He is also a co-author of a textbook on algorithms. [1]
Biography
Vazirani received a BS from MIT in 1981 [2] and received his Ph.D. in 1986 from UC Berkeley under the supervision of Manuel Blum. [3]
He is the brother of University of California, Irvine professor Vijay Vazirani.
Research
Vazirani is one of the founders of the field of quantum computing. His 1993 paper with his student Ethan Bernstein on quantum complexity theory [4] 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.
With Charles Bennett, Ethan Bernstein, and Gilles Brassard, he showed that quantum computers cannot solve black-box search problems faster than in the number of elements to be searched. This result shows that the Grover search algorithm is optimal. It also shows that quantum computers cannot solve NP-complete problems in polynomial time using only the certifier. [5] [6][ dubious ]
Awards and honors
In 2005, both Vazirani and his brother Vijay Vazirani were inducted as Fellows of the Association for Computing Machinery, Umesh for "contributions to theoretical computer science and quantum computation" [7] and his brother Vijay for his work on approximation algorithms. [8] 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). In 2018, he was elected to the National Academy of Sciences.
Selected publications
- Mulmuley, Ketan; Vazirani, Umesh V.; Vazirani, Vijay V. (1987), "Matching is as easy as matrix inversion", Combinatorica, 7 (1): 105–113, CiteSeerX 10.1.1.70.2247, doi: 10.1007/BF02579206, MR 0905157, S2CID 47370049. 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, CiteSeerX 10.1.1.655.1186, doi: 10.1145/167088.167097, ISBN 978-0897915915, S2CID 676378.
- Kearns, Michael J.; Vazirani, Umesh V. (1994), An Introduction to Computational Learning Theory, MIT Press, ISBN 9780262111935.
- 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, Bibcode: 1997quant.ph..1001B, doi: 10.1137/S0097539796300933, MR 1471991, S2CID 13403194.
References
- ^ Algorithms: Dasgupta, Papadimitriou, Vazirani
- ^ Vazirani, Umesh Virkumar (1986-01-01). Randomness, Adversaries and Computation. University of California, Berkeley.
- ^ Umesh Virkumar Vazirani at the Mathematics Genealogy Project.
- ^ Bernstein & Vazirani 1993.
- ^ Bennett, Charles H.; Bernstein, Ethan; Brassard, Gilles; Vazirani, Umesh (October 1997). "Strengths and Weaknesses of Quantum Computing". SIAM Journal on Computing. 26 (5): 1510–1523. arXiv: quant-ph/9701001. Bibcode: 1997quant.ph..1001B. doi: 10.1137/s0097539796300933. ISSN 0097-5397. S2CID 13403194.
- ^ Aaronson, Scott. "Lecture 23, Thurs April 13: BBBV, Applications of Grover" (PDF). Retrieved November 17, 2020.
- ^ ACM Fellows Award: Umesh Vazirani.
- ^ ACM Fellows Award: Vijay Vazirani.
External links
- Umesh Vazirani at UC Berkeley
| International | |
|---|---|
| National | |
| Academics | |
| Other | |
- Living people
- Indian emigrants to the United States
- 2005 Fellows of the Association for Computing Machinery
- Theoretical computer scientists
- 20th-century Indian mathematicians
- 21st-century Indian mathematicians
- 20th-century American mathematicians
- 21st-century American mathematicians
- University of California, Berkeley alumni
- UC Berkeley College of Engineering faculty
- American people of Sindhi descent
- Indian Sindhi people
- American academics of Indian descent
- Quantum information scientists
- American textbook writers
Umesh Vazirani | |
|---|---|
| Nationality | Indian–American |
| Alma mater | MIT, University of California, Berkeley |
| Known for | Bernstein-Vazirani algorithm |
| Relatives | Vijay Vazirani (brother) |
| Awards | Fulkerson Prize (2012) |
| Scientific career | |
| Fields | Quantum computation, Computational complexity |
| Institutions | University of California, Berkeley |
| Thesis | Randomness, Adversaries and Computation (1986) |
| Doctoral advisor | Manuel Blum |
| Doctoral students | |
| Website |
www |
Umesh Virkumar Vazirani is an Indian–American academic who is the Roger A. Strauch Professor of Electrical Engineering and Computer Science at the University of California, Berkeley, and the director of the Berkeley Quantum Computation Center. His research interests lie primarily in quantum computing. He is also a co-author of a textbook on algorithms. [1]
Biography
Vazirani received a BS from MIT in 1981 [2] and received his Ph.D. in 1986 from UC Berkeley under the supervision of Manuel Blum. [3]
He is the brother of University of California, Irvine professor Vijay Vazirani.
Research
Vazirani is one of the founders of the field of quantum computing. His 1993 paper with his student Ethan Bernstein on quantum complexity theory [4] 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.
With Charles Bennett, Ethan Bernstein, and Gilles Brassard, he showed that quantum computers cannot solve black-box search problems faster than in the number of elements to be searched. This result shows that the Grover search algorithm is optimal. It also shows that quantum computers cannot solve NP-complete problems in polynomial time using only the certifier. [5] [6][ dubious ]
Awards and honors
In 2005, both Vazirani and his brother Vijay Vazirani were inducted as Fellows of the Association for Computing Machinery, Umesh for "contributions to theoretical computer science and quantum computation" [7] and his brother Vijay for his work on approximation algorithms. [8] 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). In 2018, he was elected to the National Academy of Sciences.
Selected publications
- Mulmuley, Ketan; Vazirani, Umesh V.; Vazirani, Vijay V. (1987), "Matching is as easy as matrix inversion", Combinatorica, 7 (1): 105–113, CiteSeerX 10.1.1.70.2247, doi: 10.1007/BF02579206, MR 0905157, S2CID 47370049. 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, CiteSeerX 10.1.1.655.1186, doi: 10.1145/167088.167097, ISBN 978-0897915915, S2CID 676378.
- Kearns, Michael J.; Vazirani, Umesh V. (1994), An Introduction to Computational Learning Theory, MIT Press, ISBN 9780262111935.
- 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, Bibcode: 1997quant.ph..1001B, doi: 10.1137/S0097539796300933, MR 1471991, S2CID 13403194.
References
- ^ Algorithms: Dasgupta, Papadimitriou, Vazirani
- ^ Vazirani, Umesh Virkumar (1986-01-01). Randomness, Adversaries and Computation. University of California, Berkeley.
- ^ Umesh Virkumar Vazirani at the Mathematics Genealogy Project.
- ^ Bernstein & Vazirani 1993.
- ^ Bennett, Charles H.; Bernstein, Ethan; Brassard, Gilles; Vazirani, Umesh (October 1997). "Strengths and Weaknesses of Quantum Computing". SIAM Journal on Computing. 26 (5): 1510–1523. arXiv: quant-ph/9701001. Bibcode: 1997quant.ph..1001B. doi: 10.1137/s0097539796300933. ISSN 0097-5397. S2CID 13403194.
- ^ Aaronson, Scott. "Lecture 23, Thurs April 13: BBBV, Applications of Grover" (PDF). Retrieved November 17, 2020.
- ^ ACM Fellows Award: Umesh Vazirani.
- ^ ACM Fellows Award: Vijay Vazirani.
External links
- Umesh Vazirani at UC Berkeley
| International | |
|---|---|
| National | |
| Academics | |
| Other | |
- Living people
- Indian emigrants to the United States
- 2005 Fellows of the Association for Computing Machinery
- Theoretical computer scientists
- 20th-century Indian mathematicians
- 21st-century Indian mathematicians
- 20th-century American mathematicians
- 21st-century American mathematicians
- University of California, Berkeley alumni
- UC Berkeley College of Engineering faculty
- American people of Sindhi descent
- Indian Sindhi people
- American academics of Indian descent
- Quantum information scientists
- American textbook writers