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.

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

Einzelnachweise

  1. ↑ Nach Bericht der Guggenheim Foundation 2004
  2. ↑ Russell Impagliazzo. Abgerufen am 13. September 2020.
  3. ↑ Impagliazzo A personal view of average case complexity, Proceedings of the 10th Annual Structure in Complexity Theory Conference (SCT'95), 1995, S. 134
  4. ↑ Lance Fortnow, Computational Complexity Blog, 2004
  5. ↑ Impagliazzo, Paturi The Complexity of k-SAT, Proc. 14th IEEE Conf. on Computational Complexity, 1999, S. 237–240
  6. ↑ R. Impagliazzo, A. Wigderson: P=BPP if E requires exponential circuits: Derandomizing the XOR Lemma. In: 29th STOC, 1997, S. 220–229
  7. ↑ UCSD zur Guggenheim Fellowship, 2004. Er wurde für Studien zu Heuristik, Beweiskomplexität und algorithmische Techniken ausgezeichnet.
  8. ↑ Hastad, Impagliazzo Levin, Luby, A Pseudorandom Generator from any One-way Function, SIAM J. Computing, Band 28, 1999, S. 1364–1396
  9. ↑ Kurzbiografie anlässlich eines Vortrags, Univ. Michigan
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.