Umesh Virkumar Vazirani is an

Indian-American Indian Americans or Indo-Americans are citizens of the United States with ancestry from India. The United States Census Bureau uses the term Asian Indian to avoid confusion with Native Americans, who have also historically been referred t ...

academic who is the Roger A. Strauch Professor of Electrical Engineering and Computer Science at the

University of California, Berkeley The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California) is a public land-grant research university in Berkeley, California. Established in 1868 as the University of California, it is the state's first land-grant un ...

, and the director of the Berkeley Quantum Computation Center. His research interests lie primarily in

quantum computing Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Though ...

. He is also a co-author of a textbook on algorithms.Algorithms: Dasgupta, Papadimitriou, Vazirani

Biography

Vazirani received a BS from MIT in 1981 and received his Ph.D. in 1986 from UC Berkeley under the supervision of

Manuel Blum Manuel Blum (born 26 April 1938) is a Venezuelan-American computer scientist who received the Turing Award in 1995 "In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and ...

. He is the brother of

University of California, Irvine The University of California, Irvine (UCI or UC Irvine) is a public land-grant research university in Irvine, California. One of the ten campuses of the University of California system, UCI offers 87 undergraduate degrees and 129 graduate and p ...

professor

Vijay Vazirani Vijay Virkumar Vazirani ( hi, विजय वीरकुमार वज़ीरानी; b. 1957) is an Indian American distinguished professor of computer science in the Donald Bren School of Information and Computer Sciences at the Universi ...

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 Quantum complexity theory is the subfield of computational complexity theory that deals with complexity classes defined using quantum computers, a computational model based on quantum mechanics. It studies the hardness of computational proble ...

defined a model of

quantum Turing machine A quantum Turing machine (QTM) or universal quantum computer is an abstract machine used to model the effects of a quantum computer. It provides a simple model that captures all of the power of quantum computation—that is, any quantum algori ...

s 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 Peter Williston Shor (born August 14, 1959) is an American professor of applied mathematics at MIT. He is known for his work on quantum computation, in particular for devising Shor's algorithm, a quantum algorithm for factoring exponentially f ...

within a year in his celebrated quantum algorithm for factoring integers. With Charles Bennett,

Ethan Bernstein Ethan may refer to: People *Ethan (given name) Places *Ethan, South Dakota *Fort Ethan Allen (Arlington, Virginia) Fiction *''Ethan of Athos'', 1986 novel by Lois McMaster Bujold *"Ethan Brand", 1850 short story by Nathaniel Hawthorne *'' Ethan ...

, and

Gilles Brassard Gilles Brassard, is a faculty member of the Université de Montréal, where he has been a Full Professor since 1988 and Canada Research Chair since 2001. Education and early life Brassard received a Ph.D. in Computer Science from Cornell Uni ...

, he showed that quantum computers cannot solve black-box search problems faster than

O(\sqrt)

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 In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...

problems in polynomial time using only the certifier.

Awards and honors

In 2005 both Vazirani and his brother

were inducted as Fellows of the

Association for Computing Machinery The Association for Computing Machinery (ACM) is a US-based international learned society for computing. It was founded in 1947 and is the world's largest scientific and educational computing society. The ACM is a non-profit professional member ...

, Umesh for "contributions to

theoretical computer science computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumscribe the ...

and

quantum computation Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Though ...

" and his brother Vijay for his work on

approximation algorithm In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...

s.ACM Fellows Award: Vijay Vazirani
Vazirani was awarded the

Fulkerson Prize The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at e ...

for 2012 for his work on improving the approximation ratio for graph separators and related problems (jointly with

Satish Rao Satish Rao is an American computer scientist who is a professor of computer science at the University of California, Berkeley. Biography Satish Rao received his PhD from the Massachusetts Institute of Technology in 1989 and joined the facu ...

and

Sanjeev Arora Sanjeev Arora (born January 1968) is an Indian American theoretical computer scientist. Life He was a visiting scholar at the Institute for Advanced Study in 2002–03. In 2008 he was inducted as a Fellow of the Association for Computing Mach ...

). In 2018, he was elected to the

National Academy of Sciences The National Academy of Sciences (NAS) is a United States nonprofit, non-governmental organization. NAS is part of the National Academies of Sciences, Engineering, and Medicine, along with the National Academy of Engineering (NAE) and the Nat ...

Selected publications

*. A preliminary version of this paper was also published in STOC '87. *. *. *.

References

External links

Web page at UC Berkeley
{{DEFAULTSORT:Vazirani, Umesh Year of birth missing (living people) Living people Indian emigrants to the United States 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 Sindhi people American academics of Indian descent Quantum information scientists American textbook writers