Russell Impagliazzo, Ph.D.

Russell Impagliazzo has made many deep contributions to cryptography and complexity theory. Russell and collaborators showed that one-way functions exist if and only if pseudorandom generators exist. In other words, one can generate sequences of bits for which it is computationally hard to predict the next bit with accuracy much better than random guessing if and only if there are easy-to-compute functions that are hard to invert on the average. Russell also showed that there are worlds in which certain cryptographic primitives are strictly inequivalent. For example, there are worlds where one-way functions exist but public-key encryption is not possible. One of Russell’s major contributions in complexity theory is the exponential-time hypothesis and its implications. The hypothesis states that there are problems where it is hard to speed up the brute-force solution even by a small amount. Russell helped establish the first complete problem for this class. In joint work with Avi Wigderson, Russell showed that if there are problems in exponential time that require exponential-sized circuits to solve, then any efficient algorithm that uses randomization has an equivalent, efficient one that does not.