Jump to content

Russell Impagliazzo

From Wikipedia, the free encyclopedia
(Redirected from Russell Graham Impagliazzo)
Russell Graham Impagliazzo
Russell Impagliazzo at the DIMACS Workshop on Cryptography, July 2016.
Alma materWesleyan University; University of California, Berkeley
Known forResults in computational complexity theory
Scientific career
Thesis Pseudo-random Generators for Probablistic Algorithms and for Cryptography  (1992)
Doctoral advisorManuel Blum
Websitehttps://cseweb.ucsd.edu//~russell/

Russell Graham Impagliazzo[1] is a professor of computer science at the University of California, San Diego, specializing in computational complexity theory.[2]

Education

[edit]

Impagliazzo received a BA in mathematics from Wesleyan University.[3] He obtained a doctorate from the University of California, Berkeley in 1992. His advisor was Manuel Blum.[1] He joined the faculty of UCSD in 1989,[4] having been a postdoc there from 1989 to 1991.[3]

Contributions

[edit]

Impagliazzo's contributions to complexity theory include:

Five worlds of complexity theory

[edit]

Impagliazzo is well-known for proposing the "five worlds" of computational complexity theory, reflecting possible states of the world around the P versus NP problem.[16]

  1. Algorithmica: P = NP;
  2. Heuristica: P is not NP, but NP problems are tractable on average;
  3. Pessiland: there are NP problems that are hard on average, but no one-way functions;
  4. Minicrypt: one-way functions exist, but public-key cryptography does not;
  5. Cryptomania: public-key cryptography exists.

Understanding which world we live in is still a key motivating question in complexity theory and cryptography.[17]

Awards

[edit]

Impagliazzo has received the following awards:

References

[edit]
  1. ^ a b "Russell Impagliazzo - The Mathematics Genealogy Project". mathgenealogy.org. Retrieved 2021-08-30.
  2. ^ "Russell Impagliazzo's". cseweb.ucsd.edu. Retrieved 2021-08-30.
  3. ^ a b c "Russell Impagliazzo | Simons Institute for the Theory of Computing". simons.berkeley.edu. Retrieved 2021-08-30.
  4. ^ a b c d "Faculty Profile | Jacobs School of Engineering". jacobsschool.ucsd.edu. Retrieved 2021-08-30.
  5. ^ HÅstad, Johan; Impagliazzo, Russell; Levin, Leonid A.; Luby, Michael (1999). "A Pseudorandom Generator from any One-way Function" (PDF). SIAM Journal on Computing. 28 (4): 1364–1396. doi:10.1137/S0097539793244708. ISSN 0097-5397.
  6. ^ Impagliazzo, Russell (1995). "Hard-core distributions for somewhat hard problems". Proceedings of IEEE 36th Annual Foundations of Computer Science. Proceedings of IEEE 36th Annual Foundations of Computer Science. pp. 538–545. doi:10.1109/SFCS.1995.492584. ISBN 0-8186-7183-1. Retrieved 30 August 2021.
  7. ^ Beame, Paul; Impagliazzo, Russell; Krajíček, Jan; Pitassi, Toniann; Pudlák, Pavel (1996). "Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs". Proceedings of the London Mathematical Society. s3-73 (1): 1–26. doi:10.1112/plms/s3-73.1.1. ISSN 1460-244X.
  8. ^ Kabanets, Valentine; Impagliazzo, Russell (2004-12-01). "Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds". Computational Complexity. 13 (1): 1–46. doi:10.1007/s00037-004-0182-6. ISSN 1420-8954. S2CID 12451799.
  9. ^ Impagliazzo, Russell; Wigderson, Avi (1997-05-04). "P = BPP if E requires exponential circuits". Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97. El Paso, Texas, USA: Association for Computing Machinery. pp. 220–229. doi:10.1145/258533.258590. ISBN 978-0-89791-888-6. S2CID 18921599.
  10. ^ Impagliazzo, Russell (2003-04-28). "Hardness as randomness: a survey of universal derandomization". arXiv:cs/0304040.
  11. ^ Carmosino, Marco L.; Impagliazzo, Russell; Kabanets, Valentine; Kolokolova, Antonina (2015). Garg, Naveen; Jansen, Klaus; Rao, Anup; Rolim, José D. P. (eds.). "Tighter Connections between Derandomization and Circuit Lower Bounds". Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs). 40. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 645–658. doi:10.4230/LIPIcs.APPROX-RANDOM.2015.645. ISBN 978-3-939897-89-7.
  12. ^ Barak, B.; Impagliazzo, R.; Wigderson, A. (2004). "Extracting Randomness Using Few Independent Sources". 45th Annual IEEE Symposium on Foundations of Computer Science. pp. 384–393. doi:10.1109/FOCS.2004.29. ISBN 0-7695-2228-9. S2CID 7063583.
  13. ^ Impagliazzo, Russell; Paturi, Ramamohan (2001-03-01). "On the Complexity of k-SAT". Journal of Computer and System Sciences. 62 (2): 367–375. doi:10.1006/jcss.2000.1727. ISSN 0022-0000.
  14. ^ Lokshtanov, Daniel; Marx, Dániel; Saurabh, Saket (October 2011). "Lower Bounds based on the Exponential Time Hypothesis". Bulletin of the EATCS: 41–71. CiteSeerX 10.1.1.942.6217.
  15. ^ Williams, Virginia V. (2015). Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (PDF). 10th International Symposium on Parameterized and Exact Computation. pp. 17–29. doi:10.4230/LIPIcs.IPEC.2015.17.
  16. ^ Impagliazzo, Russell (April 17, 1995). "A Personal View of Average-Case Complexity".
  17. ^ Klarreich, Erica (April 18, 2022). "Which Computational Universe Do We Live In?". Quanta.
[edit]