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 to ...
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 u ...
, 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 pr ...
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 problems i ...
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
In quantum computing, the quantum Fourier transform (QFT) is a linear transformation on quantum bits, and is the quantum analogue of the discrete Fourier transform. The quantum Fourier transform is a part of many quantum algorithms, notably Shor's ...
, 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 fa ...
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
*''Eth ...
, 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 Unive ...
, 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
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 tryi ...
problems in polynomial time using only the certifier.
Awards and honors
In 2005 both Vazirani and his brother
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 ...
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
Theoretical 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 circumsc ...
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 solu ...
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 faculty ...
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 Mac ...
). 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 Nati ...
.
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