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