Russell Impagliazzo

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.
Alma mater	Wesleyan University; University of California, Berkeley
Known for	Results in computational complexity theory
Scientific career
Thesis	Pseudo-random Generators for Probablistic Algorithms and for Cryptography  (1992)
Doctoral advisor	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 postdoc 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]

1. Algorithmica: P = NP;
2. Heuristica: P is not NP, but NP problems are tractable on average;
3. Pessiland: there are NP problems that are hard on average, but no one-way functions;
4. Minicrypt: one-way functions exist, but public-key cryptography does not;
5. 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]