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. having been a postdoctoral fellow at the University of Toronto from 1989 to 1991. 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"