Russell Impagliazzo

Russell Impagliazzo is a Professor in the Department of Computer Science and Engineering at the University of California, San Diego (UCSD). He has held positions as Assistant Professor, Associate Professor, and Professor at UCSD since 1991 and was a Visiting Professor at the Institute for Advanced Study (Princeton) from 2007 to 2012. His academic journey includes a BA in Mathematics from Wesleyan University and a PhD in Mathematics from UC Berkeley.

His research focuses on computational complexity theory, with key contributions to:

• Randomness in computation
• Cryptography (e.g., pseudorandom generators)
• Circuit lower bounds
• Proof complexity (e.g., polynomial calculus, resolution)
• Structural complexity (e.g., average-case hardness)
• Optimization heuristics (e.g., local search)

The trends in his publications include foundational work on derandomization, hardness amplification, and algebraic proof systems. His papers often bridge theoretical computer science with mathematics, particularly in analyzing the limits of computational models.

Scientific awards and honors include:

• NSF Young Investigator
• Sloan Fellow
• Fulbright Scholar
• Guggenheim Fellow
• Simons Investigator
• Best Paper Award (Computational Complexity Conference)
• Best Paper Award (STOC)
• Outstanding Paper Award (SIAM)

He actively advises students and has contributed to grants and programs such as the Simons Institute’s Fine-Grained Complexity and Algorithms and the Meta-Complexity program at the Simons Lab in Spring 2023.