Russell Impagliazzo

Graham Russell Impagliazzo (* May 29, 1963 in Providence, Rhode Iceland ) is an American computer scientist who is concerned with complexity theory, cryptography and pseudo-random.

Impagliazzo attended Wesleyan University with a bachelor's degree in 1984 and in 1992 with Manuel Blum at the University of California, Berkeley PhD (pseudo - random generator for probabilistic algorithms and for cryptograp ). He is a professor at the University of California, San Diego, where he has since 1989. He had been a guest scientist at the Institute for Advanced Study.

It deals with the classification computationally hard problems, including proof complexity, randomized algorithms, pseudo- randomness, lower bounds for complexity theory and cryptography.

In 1995, he described five possible scenarios in complexity theory ( Five Worlds ): algorithmica ( in the P = NP or same applies as probabilistic algorithms for NP), Heuristica ( NP problems NP-hard in the worst case, but on average easier), Pessiland (NP- hard problems in the middle, but there is no one-way function in cryptography ), Minicrypt ( one-way function exists, but no public-key cryptography) and Crypto Mania ( public-key cryptography exists). Impagliazzo lay not determine which scenario is true, most computer scientists suspect one of the latter two. With Ramamohan Paturi 1999 he formulated the Exponential Time Hypothesis that 3- SAT and related problems in the worst case can not be solved by subexponentielle algorithms.

In 2004 he was Guggenheim Fellow. He was also a Sloan Fellow, a Fulbright Fellow, Simons Fellow and Young Investigator of the National Science Foundation.

With Valentine Kaba Nets and Avi Wigderson, he won a Best Paper Award at the Conference computational complexity, with Kaba Nets a Best Paper Award at STOC and Johan Håstad, Leonid Levin and Michael Luby an Outstanding Paper Award of the SIAM. Hastad, Impagliazzo, Levin and Luby proved that cryptographically secure pseudo-random generators exist if and only if one-way functions exist.

Writings

Besides the already cited works.

  • 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. 21st Annual ACM Symp Theory of Computing ( STOC ), 1989, pp. 12-24
  • With P = BPP if E Wigderson requires exponential circuits: Derandomizing the XOR lemma, 29th STOC 1997, 220-229
  • With Paturi, Francis Zane Which problems have 'strongly exponential complexity? , 39th FOCS 1998 ( Symp Foundations of Computer Science), 653-662
  • With Luby One -way functions are essential for complexity based cryptography, 30th FOCS, 1989, 230-235
  • Kaba Nets Derandomizing polynomial identity tests Means proving circuit lower bounds, Computational Complexity, 13, 2004, 1-46
  • Hard core distributions for somewhat hard problems, 36th FOCS 1995, 538-545
  • Kaba Nets, Wigderson In search of an easy witness: exponential time vs.. probabilistic polynomial time, Journal of Computer and System Sciences, Volume 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
  • Matthew Clegg, Jeffery Edmonds Using the Groebner basis algorithm to find proofs of unsatisfiability, 28, STOC 1996, 174-183
  • Toniann Pitassi with 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, 39th FOCS 1998, 734-743
Providence, Rhode Island Rhode Island Boolean satisfiability problem#3-satisfiability Sloan Fellows Mathematics Genealogy Project
410404
de