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.
[3] He is the brother of University of California, Irvine professor Vijay Vazirani.
With Charles Bennett, Ethan Bernstein, and Gilles Brassard, he showed that quantum computers cannot solve black-box search problems faster than
It also shows that quantum computers cannot solve NP-complete problems in polynomial time using only the certifier.
[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).