Russell Graham Impagliazzo is a professor of computer science at the University of California, San Diego. His work focuses on computational complexity theory, which studies how computers solve problems and the time needed to do so.

Education

Impagliazzo received a BA in mathematics from Wesleyan University. He earned a doctorate from the University of California, Berkeley in 1992. His advisor was Manuel Blum. He worked as a postdoc at the University of Toronto from 1989 to 1991. In 1991, he joined the faculty at UCSD.

Contributions

Impagliazzo's work in complexity theory includes:

• creating a fake random number generator using any one-way function (a function that is easy to compute but hard to reverse),
• helping prove Yao's XOR lemma using "hard core sets" (a method to analyze problem difficulty),
• proving that certain types of logical proofs, called constant-depth Hilbert proofs, must be very long to solve the pigeonhole principle,
• studying how difficult problems in computing relate to reducing the need for randomness in algorithms,
• and developing methods to create extractors that combine multiple sources of randomness without needing a seed.

He also introduced the idea that solving 3-SAT (a specific type of problem) cannot be done quickly if the number of variables is large. This idea helps scientists set limits on how fast certain computer problems can be solved.

Impagliazzo is famous for suggesting the "five worlds" of computational complexity theory, which describe possible relationships between the classes P and NP. These worlds are:

• Algorithmica: P equals NP (meaning all problems with efficient solutions can also be solved quickly).
• Heuristica: P is not equal to NP, but most problems in NP are easy to solve on average.
• Pessiland: Some problems in NP are hard on average, but no one-way functions exist.
• Minicrypt: One-way functions exist, but public-key cryptography (a method to secure information) does not.
• Cryptomania: Public-key cryptography exists.

Determining which of these worlds is true remains a major question in complexity theory and cryptography.

Awards

Impagliazzo has received the following awards:

• Received the Best Paper Award from the Computational Complexity Conference
• Received the 2003 Outstanding Paper Award from the Society for Industrial and Applied Mathematics
• Received the 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"