Russell Impagliazzo

Russell Graham Impagliazzo is a professor of computer science at the University of California, San Diego, specializing in computational complexity theory.

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 postdoc at the University of Toronto from 1989 to 1991.

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.

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.

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"

References

External links

• Russell Impagliazzo
• UCSD Jacobs, School of Engineering faculty profile