Russell Graham Impagliazzo is a professor of computer science at the

University of California, San Diego The University of California, San Diego (UC San Diego or colloquially, UCSD) is a public land-grant research university in San Diego, California. Established in 1960 near the pre-existing Scripps Institution of Oceanography, UC San Diego is t ...

specializing in computational complexity theory, having joined the faculty of UCSD in 1989. He received a BA in mathematics from

Wesleyan University Wesleyan University ( ) is a private liberal arts university in Middletown, Connecticut. Founded in 1831 as a men's college under the auspices of the Methodist Episcopal Church and with the support of prominent residents of Middletown, the col ...

. He obtained a doctorate from the

University of California, Berkeley The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California) is a public land-grant research university in Berkeley, California. Established in 1868 as the University of California, it is the state's first land-grant u ...

in 1992. His advisor was

Manuel Blum Manuel Blum (born 26 April 1938) is a Venezuelan-American 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 ...

. He is a 2004 Guggenheim fellow. Impagliazzo's contributions to complexity theory include the construction of a

pseudorandom number generator A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generate ...

from any

one-way function In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, s ...

, his proof of Yao's XOR lemma via "hard core sets", his work in propositional proof complexity, such as the exponential size lower bound for constant-depth

Hilbert David Hilbert (; ; 23 January 1862 – 14 February 1943) was a German mathematician, one of the most influential mathematicians of the 19th and early 20th centuries. Hilbert discovered and developed a broad range of fundamental ideas in many ...

proofs of the

pigeonhole principle In mathematics, the pigeonhole principle states that if items are put into containers, with , then at least one container must contain more than one item. For example, if one has three gloves (and none is ambidextrous/reversible), then there mu ...

, his work on connections between computational hardness and de-randomization, and recent 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 In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by . It states that satisfiability of 3-CNF Boolean formulas cannot be solved more quickly than exponential t ...

that

3-SAT In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfie ...

cannot be solved in subexponential time in the number of variables. This hypothesis is used to deduce lower bounds on

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...

s in

computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...

. Hi
"five worlds"
are well known in

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...

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 {{programmer-stub