Russell Impagliazzo
Encyclopedia
Russell Impagliazzo is a professor of computer science at the University of California, San Diego
. He received his doctorate from the University of California, Berkeley
. His advisor was Manuel Blum
. He spent two years as a postdoc at the University of Toronto
. He is a 2004 Guggenheim fellow. He now teaches at Princeton University, and resides at the Institute for Advanced Study in Princeton, NJ.
Impagliazzo's contributions to the field to computational complexity include: the construction of a pseudo-random generator from any one-way function, his proof of the XOR lemma via "hard core sets", his work on break through results in propositional proof complexity, such as the exponential size lower bound for constant-depth Hilbert proofs of the pigeonhole principle and the introduction of the polynomial calculus system, his work on connections between computational hardness and derandomization, and a recent break-through work on the construction of multi-source seedless extractors. He has contributed to 40 papers on topics within his specialties.
His "five worlds" http://cseweb.ucsd.edu/users/russell/average.ps are well-known in computational complexity theory
.
University of California, San Diego
The University of California, San Diego, commonly known as UCSD or UC San Diego, is a public research university located in the La Jolla neighborhood of San Diego, California, United States...
. He received his doctorate from the University of California, Berkeley
University of California, Berkeley
The University of California, Berkeley , is a teaching and research university established in 1868 and located in Berkeley, California, USA...
. His advisor was Manuel Blum
Manuel Blum
Manuel Blum is a computer scientist who received the Turing Award in 1995 "In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and program checking".-Biography:Blum attended MIT, where he received his bachelor's degree and...
. He spent two years as a postdoc at the University of Toronto
University of Toronto
The University of Toronto is a public research university in Toronto, Ontario, Canada, situated on the grounds that surround Queen's Park. It was founded by royal charter in 1827 as King's College, the first institution of higher learning in Upper Canada...
. He is a 2004 Guggenheim fellow. He now teaches at Princeton University, and resides at the Institute for Advanced Study in Princeton, NJ.
Impagliazzo's contributions to the field to computational complexity include: the construction of a pseudo-random generator from any one-way function, his proof of the XOR lemma via "hard core sets", his work on break through results in propositional proof complexity, such as the exponential size lower bound for constant-depth Hilbert proofs of the pigeonhole principle and the introduction of the polynomial calculus system, his work on connections between computational hardness and derandomization, and a recent break-through work on the construction of multi-source seedless extractors. He has contributed to 40 papers on topics within his specialties.
His "five worlds" http://cseweb.ucsd.edu/users/russell/average.ps are well-known in computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
.