Sanjeev Arora
Encyclopedia
Sanjeev Arora is a theoretical computer scientist who is best known for his work on probabilistically checkable proofs and, in particular, the PCP theorem
. He is currently the Charles C. Fitzmorris Professor of Computer Science at Princeton University
, and his research interests include computational complexity theory
, uses of randomness
in computation, probabilistically checkable proofs, computing approximate
solutions to NP-hard
problems, and geometric embeddings of metric spaces.
He received the S.B. in Mathematics with Computer Science from MIT in 1990 and received a Ph.D. in Computer Science from the University of California, Berkeley
in 1994 under Umesh Vazirani
.
His Ph.D. thesis on probabilistically checkable proofs received the ACM Doctoral Dissertation Award in 1995. He was awarded the Gödel Prize
for his work on the PCP theorem in 2001 and again in 2010 for the discovery (concurrently with Joseph S. B. Mitchell
) of a polynomial time approximation scheme for the euclidean travelling salesman problem. In 2008 he was inducted as a Fellow of the Association for Computing Machinery
.
He is a coauthor (with Boaz Barak) of the book "Computational Complexity: A Modern Approach".
PCP theorem
In computational complexity theory, the PCP theorem states that every decision problem in the NP complexity class has probabilistically checkable proofs of constant query complexity and logarithmic randomness complexity .The PCP theorem says that for some universal constant K, for every...
. He is currently the Charles C. Fitzmorris Professor of Computer Science at Princeton University
Princeton University
Princeton University is a private research university located in Princeton, New Jersey, United States. The school is one of the eight universities of the Ivy League, and is one of the nine Colonial Colleges founded before the American Revolution....
, and his research interests include computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, uses of randomness
Randomized algorithm
A randomized algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits...
in computation, probabilistically checkable proofs, computing approximate
Approximation algorithm
In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...
solutions to NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
problems, and geometric embeddings of metric spaces.
He received the S.B. in Mathematics with Computer Science from MIT in 1990 and received a Ph.D. in Computer Science from the University of California, Berkeley
University of California, Berkeley
The University of California, Berkeley , is a teaching and research university established in 1868 and located in Berkeley, California, USA...
in 1994 under Umesh Vazirani
Umesh Vazirani
Umesh Virkumar Vazirani 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. Vazirani was himself a Ph.D. student at Berkeley, receiving his Ph.D. in 1986 under the...
.
His Ph.D. thesis on probabilistically checkable proofs received the ACM Doctoral Dissertation Award in 1995. He was awarded the Gödel Prize
Gödel Prize
The Gödel Prize is a prize for outstanding papers in theoretical computer science, named after Kurt Gödel and awarded jointly by the European Association for Theoretical Computer Science and the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory .The...
for his work on the PCP theorem in 2001 and again in 2010 for the discovery (concurrently with Joseph S. B. Mitchell
Joseph S. B. Mitchell
Joseph S. B. Mitchell is an American computer scientist and mathematician. He is Professor of Applied Mathematics and Statistics and Research Professor of Computer Science at the Stony Brook University.-Biography:...
) of a polynomial time approximation scheme for the euclidean travelling salesman problem. In 2008 he was inducted as a Fellow of the Association for Computing Machinery
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
.
He is a coauthor (with Boaz Barak) of the book "Computational Complexity: A Modern Approach".