fbpx
Wikipedia

Russell Impagliazzo

December 02, 2023

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

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
ThesisPseudo-random Generators for Probablistic Algorithms and for Cryptography (1992)
Doctoral advisorManuel Blum
Websitehttps://cseweb.ucsd.edu//~russell/

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). 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. 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.

External links edit

  • Russell Impagliazzo
  • UCSD Jacobs, School of Engineering faculty profile

December 02, 2023
russell, impagliazzo, russell, graham, impagliazzo, professor, computer, science, university, california, diego, specializing, computational, complexity, theory, russell, graham, impagliazzo, dimacs, workshop, cryptography, july, 2016, alma, materwesleyan, uni. Russell Graham Impagliazzo 1 is a professor of computer science at the University of California San Diego specializing in computational complexity theory 2 Russell Graham ImpagliazzoRussell Impagliazzo at the DIMACS Workshop on Cryptography July 2016 Alma materWesleyan University University of California BerkeleyKnown forResults in computational complexity theoryScientific careerThesisPseudo random Generators for Probablistic Algorithms and for Cryptography 1992 Doctoral advisorManuel BlumWebsitehttps cseweb ucsd edu russell Contents 1 Education 2 Contributions 2 1 Five worlds of complexity theory 3 Awards 4 References 5 External linksEducation editImpagliazzo 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 editImpagliazzo 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 proof of 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 his work on the construction of multi source seedless extractors 12 stating 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 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 Algorithmica P NP Heuristica P is not NP but NP problems are tractable on average Pessiland there are NP problems that are hard on average but no one way functions Minicrypt one way functions exist but public key cryptography does not Cryptomania public key cryptography exists Understanding which world we live in is still a key motivating question in complexity theory and cryptography 17 Awards editImpagliazzo has received the following awards Best Paper Award from the Computational Complexity Conference 3 2003 Outstanding Paper Award from the Society for Industrial and Applied Mathematics 4 2003 Best Paper Award at the Symposium on Theory of Computing 4 named a 2004 Guggenheim fellow for work on heuristics proof complexity and algorithmic techniques 4 References edit a b Russell Impagliazzo The Mathematics Genealogy Project mathgenealogy org Retrieved 2021 08 30 Russell Impagliazzo s cseweb ucsd edu Retrieved 2021 08 30 a b c Russell Impagliazzo Simons Institute for the Theory of Computing simons berkeley edu Retrieved 2021 08 30 a b c d Faculty Profile Jacobs School of Engineering jacobsschool ucsd edu Retrieved 2021 08 30 HAstad 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 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 Beame Paul Impagliazzo Russell Krajicek Jan Pitassi Toniann Pudlak 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 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 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 Impagliazzo Russell 2003 04 28 Hardness as randomness a survey of universal derandomization arXiv cs 0304040 Carmosino Marco L Impagliazzo Russell Kabanets Valentine Kolokolova Antonina 2015 Garg Naveen Jansen Klaus Rao Anup Rolim Jose 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 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 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 Lokshtanov Daniel Marx Daniel Saurabh Saket October 2011 Lower Bounds based on the Exponential Time Hypothesis Bulletin of the EATCS 41 71 CiteSeerX 10 1 1 942 6217 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 Impagliazzo Russell April 17 1995 A Personal View of Average Case Complexity Klarreich Erica April 18 2022 Which Computational Universe Do We Live In Quanta External links editRussell Impagliazzo UCSD Jacobs School of Engineering faculty profile Retrieved from https en wikipedia org w index php title Russell Impagliazzo amp oldid 1184684060, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.