Russell Impagliazzo

From Wikipedia, the free encyclopedia
Russell Graham Impagliazzo
Russell Impagliazzo at the DIMACS Workshop on Cryptography.jpg
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
ThesisPseudo-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] having joined the faculty of UCSD in 1989.[3] He received a BA in mathematics from Wesleyan University.[4] He obtained a doctorate from the University of California, Berkeley in 1992. His advisor was Manuel Blum.[1] He is a 2004 Guggenheim fellow.[3]

Impagliazzo's contributions to complexity theory include the construction of a pseudorandom number generator from any one-way function,[5] his proof of Yao's XOR lemma via "hard core sets",[6] his work in propositional proof complexity, such as the exponential size lower bound for constant-depth Hilbert proofs of the pigeonhole principle[7], his work on connections between computational hardness and de-randomization,[8][9][10][11] and recent[citation needed] work on the construction of multi-source seedless extractors.[12][verification needed]

Impagliazzo has contributed to more than 40[quantify] papers on topics within his specialties.[citation needed] He also stated the exponential time hypothesis that 3-SAT cannot be solved in subexponential time in the number of variables.[13] This hypothesis is used to deduce lower bounds on algorithms in computer science.[14][15]

His "five worlds" are well known in computational complexity theory.[citation needed]

References[]

  1. ^ Jump up to: 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. ^ Jump up to: a b "Faculty Profile | Jacobs School of Engineering". jacobsschool.ucsd.edu. Retrieved 2021-08-30.
  4. ^ "Russell Impagliazzo | Simons Institute for the Theory of Computing". simons.berkeley.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. 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: derandomizing the XOR lemma". Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing. STOC '97. El Paso, Texas, USA: Association for Computing Machinery: 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). Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. 40: 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: 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" (PDF). 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.

External links[]


Stub icon

This biographical article relating to a computer specialist is a stub. You can help Wikipedia by .

  • v
  • t
Retrieved from ""