Russell Impagliazzo

Russell Graham Impagliazzo (* 29. Mai 1963 in Providence, Rhode Island) ist ein US-amerikanischer Informatiker, der sich mit Komplexitätstheorie, Pseudozufall und Kryptographie befasst.

Impagliazzo studierte an der Wesleyan University mit dem Bachelor-Abschluss 1984 und wurde 1992 bei Manuel Blum an der University of California, Berkeley promoviert (Pseudo-random generators for cryptography and for randomized algorithms). Er ist Professor an der University of California, San Diego, an der er seit 1989 ist. Er war mehrfach Gastwissenschaftler am Institute for Advanced Study.

Er befasst sich mit der Klassifikation rechnerisch schwerer Probleme, einschließlich Beweiskomplexität, randomisierte Algorithmen, Pseudozufälligkeit, untere Grenzen für Komplexität und Theorie der Kryptographie.

1995 beschrieb er fünf mögliche Szenarien in der Komplexitätstheorie (Five Worlds): Algorithmica (in der P=NP oder Ähnliches gilt wie probabilistische Algorithmen für NP), Heuristica (NP-Probleme NP-schwer im schlimmsten fall, im Mittel aber einfacher), Pessiland (NP-Probleme schwer im Mittel, es existiert aber keine Einwegfunktion für die Kryptographie), Minicrypt (Einwegfunktion existiert, aber keine Public-Key-Kryptographie) und Cryptomania (Public-Key-Kryptographie existiert). Impagliazzo legte sich nicht fest, welches Szenario zutrifft, die meisten Informatiker vermuten eines der beiden letzteren. Mit Ramamohan Paturi formulierte er 1999 die Exponential Time Hypothesis, dass 3-SAT und ähnliche Probleme im schlimmsten Fall nicht durch subexponentielle Algorithmen gelöst werden können.

1997 zeigte er mit Avi Wigderson, dass unter bestimmten Bedingungen schnelle Zufallsalgorithmen immer in deterministische Algorithmen umgewandelt werden können (durch Konstruktion geeigneter Pseudozufallsgeneratoren): die Komplexitätsklasse BPP ist unter einer häufig als zutreffend angenommenen Voraussetzung gleich der Komplexitätsklasse P. Die Voraussetzung ist das die Komplexitätsklasse E exponentielle Schaltkreiskomplexität hat.

2004 war er Guggenheim Fellow. Außerdem war er Sloan Research Fellow (1994–1996), Fulbright Fellow, Simons Fellow und Young Investigator der National Science Foundation.

Mit Valentine Kabanets und Avi Wigderson gewann er einen Best Paper Award auf der Computational Complexity Conference, mit Kabanets einen Best Paper Award auf der STOC und mit Johan Håstad, Leonid Levin und Michael Luby einen Outstanding Paper Award der SIAM. Hastad, Impagliazzo, Levin und Luby bewiesen darin, dass kryptografisch sichere Pseudozufallsgeneratoren genau dann existieren, wenn Einweg-Funktionen existieren.