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 in communications material, formerly and colloquially UCSD) is a public university, public Land-grant university, land-grant research university in San Diego, California, United States. Es ...

, specializing in

computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations ...

theory.

Education

Impagliazzo received a BA in mathematics from

Wesleyan University Wesleyan University ( ) is a Private university, private liberal arts college, liberal arts university in Middletown, Connecticut, United States. It was founded in 1831 as a Men's colleges in the United States, men's college under the Methodi ...

. He obtained a doctorate from the

University of California, Berkeley The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California), is a Public university, public Land-grant university, land-grant research university in Berkeley, California, United States. Founded in 1868 and named after t ...

in 1992. His advisor was

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

. He joined the faculty of UCSD in 1991, having been a postdoc at the University of Toronto from 1989 to 1991.

Contributions

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 number generation, random n ...

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 In cryptography and the theory of computation, Yao's test is a test defined by Andrew Chi-Chih Yao in 1982,Andrew Chi-Chih YaoTheory and applications of trapdoor functions In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science ...

via "hard core sets", * his proof of the exponential size lower bound for constant-depth

Hilbert David Hilbert (; ; 23 January 1862 – 14 February 1943) was a German mathematician and philosophy of mathematics, philosopher of mathematics and one of the most influential mathematicians of his time. Hilbert discovered and developed a broad ...

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, of three gloves, at least two must be right-handed or at least two must be l ...

, * 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 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 in subexponential time, 2^. Mor ...

that

3-SAT In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) asks whether there exists an interpretation that satisfies a given Boolean f ...

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 Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...

s in

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

Five worlds of complexity theory

Impagliazzo is well-known for proposing the "five worlds" of

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...

, reflecting possible states of the world around the

P versus NP problem The P versus NP problem is a major unsolved problem in theoretical computer science. Informally, it asks whether every problem whose solution can be quickly verified can also be quickly solved. Here, "quickly" means an algorithm exists that ...

. # Algorithmica: P = NP; # Heuristica: P is not NP, but NP problems are tractable on average; # Pessiland: there are NP problems that are hard on average, but no

s; # Minicrypt: one-way functions exist, but

public-key cryptography Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...

does not; # Cryptomania: public-key cryptography exists. Understanding which world we live in is still a key motivating question in complexity theory and cryptography.

Awards

Impagliazzo has received the following awards: * Best Paper Award from the

Computational Complexity Conference The Computational Complexity Conference (CCC) is an academic conference in the field of theoretical computer science whose roots date to 1986. It fosters research in computational complexity theory In theoretical computer science and mathematic ...

* 2003 Outstanding Paper Award from the

Society for Industrial and Applied Mathematics Society for Industrial and Applied Mathematics (SIAM) is a professional society dedicated to applied mathematics, computational science, and data science through research, publications, and community. SIAM is the world's largest scientific soci ...

* 2003 Best Paper Award at the

Symposium on Theory of Computing The Annual ACM Symposium on Theory of Computing (STOC) is an academic conference in the field of theoretical computer science. STOC has been organized annually since 1969, typically in May or June; the conference is sponsored by the Association for ...

* 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
{{DEFAULTSORT:Impagliazzo, Russell 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