Russell Impagliazzo
American computer scientist
- 1 min read
- 3 chapters
Related on Lably
Through Algorithm and Computer science
Education
Impagliazzo received a BA in mathematics from Wesleyan University. He obtained a doctorate from the University of California, Berkeley in 1992. His advisor was Manuel Blum. He joined the faculty of UCSD in 1991, having been a postdoctoral fellow at the University of Toronto from 1989 to 1991.
Sign in to keep reading
2 more chapters are free with a Lably account.
Contributions
Impagliazzo's contributions to complexity theory include:
- the construction of a pseudorandom number generator from any one-way function,
- his proof of Yao's XOR lemma via "hard core sets",
- his proof of the exponential size lower bound for constant-depth Hilbert proofs of the pigeonhole principle,
- his work on connections between computational hardness and de-randomization,
- and his work on the construction of multi-source seedless extractors.
- stating the exponential time hypothesis that 3-SAT cannot be solved in subexponential time in the number of variables, This hypothesis is used to deduce lower bounds on algorithms in computer science.
Five worlds of complexity theory
Impagliazzo is well known for proposing the "five worlds" of computational complexity theory, reflecting possible states of the world around the P versus NP problem.
- Algorithmica: P = NP;
- Heuristica: P is not NP, but NP problems are tractable on average;
- Pessiland: there are NP problems that are hard on average, but no one-way functions;
- Minicrypt: one-way functions exist, but public-key cryptography does not;
- Cryptomania: public-key cryptography exists.
Understanding which world we live in is still a key motivating question in complexity theory and cryptography.
Awards
Impagliazzo has received the following awards:
- Best Paper Award from the Computational Complexity Conference
- 2003 Outstanding Paper Award from the Society for Industrial and Applied Mathematics
- 2003 Best Paper Award at the Symposium on Theory of Computing
- named a 2004 Guggenheim fellow for work on "heuristics, proof complexity, and algorithmic techniques"