Russell Impagliazzo
American computer scientist
From Wikipedia, the free encyclopedia
Russell Graham Impagliazzo[1] is a professor of computer science at the University of California, San Diego, specializing in computational complexity theory.[2]
Russell Graham Impagliazzo | |
|---|---|
Russell Impagliazzo at the DIMACS Workshop on Cryptography, July 2016. | |
| Education | Wesleyan University University of California, Berkeley |
| Known for | Results in computational complexity theory |
| Scientific career | |
| Thesis | Pseudo-random Generators for Probabilistic Algorithms and for Cryptography (1992) |
| Manuel Blum | |
| Website | https://cseweb.ucsd.edu//~russell/ |
Education
Impagliazzo received a BA in mathematics from Wesleyan University.[3] He obtained a doctorate from the University of California, Berkeley in 1992. His advisor was Manuel Blum.[1] He joined the faculty of UCSD in 1991,[4] having been a postdoctoral fellow at the University of Toronto from 1989 to 1991.[3]
Contributions
Impagliazzo's contributions to complexity theory include:
- the construction of a pseudorandom number generator from any one-way function,[5]
- his proof of Yao's XOR lemma via "hard core sets",[6]
- his proof of the exponential size lower bound for constant-depth Hilbert proofs of the pigeonhole principle,[7]
- his work on connections between computational hardness and de-randomization,[8][9][10][11]
- and his work on the construction of multi-source seedless extractors.[12]
- stating the exponential time hypothesis that 3-SAT cannot be solved in subexponential time in the number of variables,[13] This hypothesis is used to deduce lower bounds on algorithms in computer science.[14][15]
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.[16]
- 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.[17]
Awards
Impagliazzo has received the following awards:
- Best Paper Award from the Computational Complexity Conference[3]
- 2003 Outstanding Paper Award from the Society for Industrial and Applied Mathematics[4]
- 2003 Best Paper Award at the Symposium on Theory of Computing[4]
- named a 2004 Guggenheim fellow for work on "heuristics, proof complexity, and algorithmic techniques"[4]