Russell Impagliazzo

An American theoretical computer scientist at the University of California, San Diego, known for proposing the Exponential Time Hypothesis and the 'five worlds' of complexity.

1 articleLast mentioned

Russell Impagliazzo is an American theoretical computer scientist and a professor of computer science at the University of California, San Diego. He received his PhD from the University of California, Berkeley under Manuel Blum, and his research covers computational complexity theory, cryptography, and pseudorandomness.

Together with Ramamohan Paturi he proposed the Exponential Time Hypothesis (ETH) while studying the complexity of k-SAT. In 1995 he introduced the widely cited 'five worlds' framework, which classifies possible universes according to the relationship between P versus NP and cryptography as Algorithmica, Heuristica, Pessiland, Minicrypt, and Cryptomania. The Impagliazzo–Wigderson theorem on pseudorandom generators and derandomization also bears his name.

This entry is based on AIPOST articles and widely known facts. If something is wrong, please send us a correction request.

Articles covering this entry

  • ETH Disproof by OpenAI's AI: What Changes for P vs NP and CryptographyAI News ·

    The hypothesis, proposed roughly three decades ago by Russell Impagliazzo, Ramamohan Paturi and Francis Zane, asserted that solving the k-CNF version of this pr…

    Read article

Found a mistake or missing an entry?

Wiki entries are based on AIPOST articles and widely known facts. If an entry is wrong, send us a correction request and we will check and fix it. Names from new articles are added to the wiki after the article is published.