Russell Impagliazzo

from Wikipedia, the free encyclopedia
Russell Impagliazzo

Russell Graham Impagliazzo (born May 29, 1963 in Providence , Rhode Island ) is an American computer scientist who deals with complexity theory , pseudorandom and cryptography .

Impagliazzo studied at Wesleyan University with a bachelor's degree in 1984 and received his doctorate in 1992 under Manuel Blum at the University of California, Berkeley ( pseudo-random generators for probabilistic algorithms and for cryptograp ). He is a professor at the University of California, San Diego , where he has been since 1989. He was visiting scholar at the Institute for Advanced Study several times .

He deals with the classification of computationally difficult problems, including evidence complexity, randomized algorithms, pseudorandomness, lower bounds on complexity, and theory of cryptography.

In 1995 he described five possible scenarios in complexity theory ( Five Worlds ): Algorithmica (in which P = NP or the like applies like probabilistic algorithms for NP ), Heuristica (NP problems NP-difficult in the worst case, but on average easier), Pessiland (NP problems difficult on average, but there is no one-way function for cryptography), Minicrypt (one-way function exists, but no public-key cryptography ) and Cryptomania (public-key cryptography exists). Impagliazzo did not decide which scenario applies, most computer scientists suspect one of the latter two. With Ramamohan Paturi in 1999 he formulated the Exponential Time Hypothesis that 3-SAT and similar problems cannot be solved by sub-exponential algorithms in the worst case.

In 2004 he was a Guggenheim Fellow . He was also a Sloan Research Fellow (1994–1996), Fulbright Fellow, Simons Fellow and Young Investigator of the National Science Foundation.

With Valentine Kabanets and Avi Wigderson he won a Best Paper Award at the Computational Complexity Conference, with Kabanets a Best Paper Award at the STOC and with Johan Håstad , Leonid Levin and Michael Luby an Outstanding Paper Award from SIAM. Hastad, Impagliazzo, Levin and Luby proved that cryptographically secure pseudo-random generators exist precisely when one-way functions exist.

Fonts

Except for the works already cited.

  • with M. Jakobsson, K. Sako Designated verifier proofs and their applications , Eurocrypt 96, 143–154
  • with Levin, Luby Pseudo-random generation from one-way functions , Proc. 21. Annual ACM Symp. Theory of Computing (STOC), 1989, pp. 12-24
  • with 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
  • with 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, Vol. 65, 200, pp. 672-694
  • with Boaz Barak, Oded Goldreich , Steven Rudich , Amit Sahai, Salil Vadhan, Ke Yang On the (im) possibility of obfuscating programs , Crypto 2001, 1–18
  • with Matthew Clegg, Jeffery Edmonds Using the Groebner basis algorithm to find proofs of unsatisfiability , 28th STOC 1996, 174-183
  • with Toniann Pitassi, Paul Beame Exponential lower bounds for the pigeonhole principle , Computational Complexity, Volume 3, 1993, 97-140
  • with Wigderson Randomness vs. time: de-randomization under a uniform assumption , 39. FOCS 1998, 734-743

Web links

Individual evidence

  1. ^ Based on a report by the Guggenheim Foundation 2004
  2. ↑ Russell Impagliazzo in the Mathematics Genealogy Project (English)Template: MathGenealogyProject / Maintenance / id used
  3. ↑ Impagliazzo A personal view of average case complexity , Proceedings of the 10th Annual Structure in Complexity Theory Conference (SCT'95), 1995, p. 134
  4. ^ Lance Fortnow, Computational Complexity Blog, 2004
  5. ^ Impagliazzo, Paturi The Complexity of k-SAT , Proc. 14th IEEE Conf. on Computational Complexity, 1999, pp. 237-240
  6. ^ UCSD on the Guggenheim Fellowship, 2004 . He was recognized for studies on heuristics, evidence complexity, and algorithmic techniques .
  7. ↑ Hastad, Impagliazzo Levin, Luby, A pseudorandom generator from any one-way function , SIAM J. Computing, vol 28, 1999, pp 1364-1396
  8. ↑ Short biography on the occasion of a lecture, Univ. Michigan
personal data
SURNAME Impagliazzo, Russell
ALTERNATIVE NAMES Impagliazzo, Russell Graham
BRIEF DESCRIPTION American computer scientist
DATE OF BIRTH May 29, 1963
PLACE OF BIRTH Providence , Rhode Island