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 1989, having been a postdoc there 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. proposing the "five worlds" of computational complexity theory. 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 American computer scientists University of California, San Diego faculty University of California, Berkeley alumni University of Toronto people Living people Simons Investigator Year of birth missing (living people) 21st-century American mathematicians 20th-century American mathematicians