Russell_Impagliazzo Knowpia

Russell Graham Impagliazzo
Russell Graham Impagliazzo
	Russell Impagliazzo at the DIMACS Workshop on Cryptography, July 2016.
Alma mater	Wesleyan University; University of California, Berkeley
Known for	Results in computational complexity theory
	Scientific career
Thesis	Pseudo-random Generators for Probablistic Algorithms and for Cryptography (1992)
Doctoral advisor	Manuel Blum
Website	https://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:

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 edit

Impagliazzo 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.
^ 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.
^ 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; 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.
^ 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, 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.
^ 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, 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.
^ 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 edit

Russell Impagliazzo
UCSD Jacobs, School of Engineering faculty profile

[:0-1] "Russell Impagliazzo - The Mathematics Genealogy Project". mathgenealogy.org. Retrieved 2021-08-30.

[2] "Russell Impagliazzo's". cseweb.ucsd.edu. Retrieved 2021-08-30.

[simons-3] "Russell Impagliazzo | Simons Institute for the Theory of Computing". simons.berkeley.edu. Retrieved 2021-08-30.

[:1-4] "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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]