Russell Impagliazzo
 |
This article includes a list of references, related reading or external links, but its sources remain unclear because it lacks inline citations. Please improve this article by introducing more precise citations. (May 2009) |
 |
The topic of this article may not meet Wikipedia's notability guideline for academics. Please help to establish notability by adding reliable, secondary sources about the topic. If notability cannot be established, the article is likely to be merged, redirected, or deleted. (May 2009) |
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" [1] are well-known in computational complexity theory.
[edit] External links
 |
This biographical article relating to a computer specialist is a stub. You can help Wikipedia by expanding it. |
