Russell Impagliazzo

Russell Impagliazzo is a Professor in the Department of Computer Science and Engineering at the Jacobs School of Engineering, University of California, San Diego, where he conducts foundational research in theoretical computer science.

His work centers on Cryptography and Computational Complexity, with seminal contributions including the equivalence proof between one-way functions and pseudorandom generators, the framework of cryptographic "worlds" demonstrating strict inequivalence of primitives (e.g., one-way functions without public-key encryption), and the exponential-time hypothesis (ETH) characterizing problems resisting brute-force speedups. His collaboration with Avi Wigderson established critical links between circuit lower bounds and derandomization, showing that exponential circuit complexity for EXP problems implies P = BPP.

Impagliazzo's research trends emphasize structural relationships in complexity classes and cryptographic feasibility, with subfields spanning average-case hardness, pseudorandomness, and fine-grained complexity. His theoretical frameworks remain highly influential in advancing computational hardness assumptions.