Russell Impagliazzo: Difference between revisions
minor improvements and puffery reduction |
Postdoc joke is funny but I removed it. |
||
| Line 7: | Line 7: | ||
}} |
}} |
||
'''Russell Impagliazzo''' is a professor of computer science at the [[University of California, San Diego]] specializing in [[computational complexity]] theory. He obtained a doctorate from the [[University of California, Berkeley]]. His advisor was [[Manuel Blum]]. |
'''Russell Impagliazzo''' is a professor of computer science at the [[University of California, San Diego]] specializing in [[computational complexity]] theory. He obtained a doctorate from the [[University of California, Berkeley]]. His advisor was [[Manuel Blum]]. He is a [[List of Guggenheim Fellowships awarded in 2004|2004 Guggenheim fellow]]. |
||
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 work on break through results in propositional proof complexity, such as the exponential size lower bound for constant-depth [[David Hilbert|Hilbert]] proofs of the [[pigeonhole principle]] and the introduction of the polynomial calculus system, his work on connections between computational hardness and de-randomization, and recent{{Citation needed|reason=Avoid use of "recent" or "today" or relative timing references, unless you state a clarifying date in parentheses|date=July 2019}} break-through work on the construction of multi-source seedless extractors. |
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 work on break through results in propositional proof complexity, such as the exponential size lower bound for constant-depth [[David Hilbert|Hilbert]] proofs of the [[pigeonhole principle]] and the introduction of the polynomial calculus system, his work on connections between computational hardness and de-randomization, and recent{{Citation needed|reason=Avoid use of "recent" or "today" or relative timing references, unless you state a clarifying date in parentheses|date=July 2019}} break-through work on the construction of multi-source seedless extractors. |
||
Revision as of 16:39, 28 May 2020
 | This article includes a list of general references, but it lacks sufficient corresponding inline citations. (May 2009) |
Russell Impagliazzo | |
|---|---|
 Russell Impagliazzo at the DIMACS Workshop on Cryptography, July 2016. |
Russell Impagliazzo is a professor of computer science at the University of California, San Diego specializing in computational complexity theory. He obtained a doctorate from the University of California, Berkeley. His advisor was Manuel Blum. He is a 2004 Guggenheim fellow.
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 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 de-randomization, and recent[citation needed] break-through work on the construction of multi-source seedless extractors.
Impagliazzo has contributed to more than 40 papers on topics within his specialties. He also stated the exponential time hypothesis that 3-SAT cannot be solved in subexponential time in the number of variables. This hypothesis is used to deduce many lower bounds on algorithms in computer science.
His "five worlds" are well known in computational complexity theory.
References
External links
| International | |
|---|---|
| Academics | |
 | This biographical article relating to a computer specialist is a stub. You can help Wikipedia by expanding it. |