mini|Russell Impagliazzo Russell Graham Impagliazzo (* 29. Mai 1963 in Providence, Rhode IslandNach Bericht der Guggenheim Foundation 2004) 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 A personal view of average case complexity, Proceedings of the 10th Annual Structure in Complexity Theory Conference (SCT'95), 1995, S. 134 Impagliazzo legte sich nicht fest, welches Szenario zutrifft, die meisten Informatiker vermuten eines der beiden letzteren.Lance Fortnow, Computational Complexity Blog, 2004 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.Impagliazzo, Paturi The Complexity of k-SAT, Proc. 14th IEEE Conf. on Computational Complexity, 1999, S. 237–240
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.R. Impagliazzo, A. Wigderson: P=BPP if E requires exponential circuits: Derandomizing the XOR Lemma. In: 29th STOC, 1997, S. 220–229 Die Voraussetzung ist das die Komplexitätsklasse E exponentielle Schaltkreiskomplexität hat.
2004 war er Guggenheim Fellow.UCSD zur Guggenheim Fellowship, 2004. Er wurde für Studien zu Heuristik, Beweiskomplexität und algorithmische Techniken ausgezeichnet. 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 LubyHastad, Impagliazzo Levin, Luby, A Pseudorandom Generator from any One-way Function, SIAM J. Computing, Band 28, 1999, S. 1364–1396 einen Outstanding Paper Award der SIAM.Kurzbiografie anlässlich eines Vortrags, Univ. Michigan Hastad, Impagliazzo, Levin und Luby bewiesen darin, dass kryptografisch sichere Pseudozufallsgeneratoren genau dann existieren, wenn Einweg-Funktionen existieren.
2025 wurde Impagliazzo zum Mitglied der National Academy of Sciences gewählt.
Schriften Außer den bereits zitierten Arbeiten. mit M. Jakobsson, K. Sako Designated verifier proofs and their applications, Eurocrypt 96, 143–154 mit Levin, Luby Pseudo-random generation from one-way functions, Proc. 21. Annual ACM Symp. Theory of Computing (STOC), 1989, S. 12–24 mit Wigderson P= BPP if E requires exponential circuits: Derandomizing the XOR lemma, 29. STOC 1997, 220–229 mit Paturi, Francis Zane Which problems have strongly exponential complexity ?, 39. FOCS 1998 (Symp. Foundations of Computer Science), 653–662 mit Luby One-way functions are essential for complexity based cryptography, 30. FOCS 1989, 230–235 mit Kabanets Derandomizing polynomial identity tests means proving circuit lower bounds, Computational Complexity, 13, 2004, 1–46 Hard core distributions for somewhat hard problems, 36. FOCS 1995, 538–545 mit Kabanets, Wigderson In search of an easy witness: exponential time vs. probabilistic polynomial time, Journal of Computer and System Sciences, Band 65, 200, S. 672–694 mit Boaz Barak, Oded Goldreich, Steven Rudich, Amit Sahai, Salil Vadhan, Ke Yang On the (im) possibility of obfuscating programs, Crypto 2001, 1–18 mit Matthew Clegg, Jeffery Edmonds Using the Groebner basis algorithm to find proofs of unsatisfiability, 28. STOC 1996, 174–183 mit Toniann Pitassi, Paul Beame Exponential lower bounds for the pigeonhole principle, Computational Complexity, Band 3, 1993, 97–140 mit Wigderson Randomness vs. time: de-randomization under a uniform assumption, 39. FOCS 1998, 734–743
Weblinks Homepage
Einzelnachweise
Kategorie:Informatiker Kategorie:Hochschullehrer (University of California, San Diego) Kategorie:Mitglied der National Academy of Sciences Kategorie:US-Amerikaner Kategorie:Geboren 1963 Kategorie:Mann