Russell Impagliazzo

Impagliazzo's primary research area is in computational complexity, the study of the inherent computational difficulty of problems. His work in computational complexity often connects to other areas of computer science and mathematics, such as algorithm design, logic, combinatorics, machine learning, and the foundations of cryptography. One long-standing interest is in the complexity theory of randomness, giving formal senses in which making randomized algorithms deterministic requires proving functions are computationally hard. He also works in proof complexity, demonstrating tautologies that require long proofs in formal proof systems. Another long-term project is to unravel the many connections between boosting (a technique in machine learning), average-case complexity, pseudo-randomness, regularity theorems in combinatorics, and generative algorithms in machine learning. He and his co-authors recently introduced a formal model of replicable algorithms, which, with high probability, have identical outputs even when run on different datasets.