Russell Impagliazzo Explained

Russell Graham Impagliazzo
Alma Mater:	Wesleyan University University of California, Berkeley
Thesis Title:	Pseudo-random Generators for Probablistic Algorithms and for Cryptography
Thesis Year:	1992
Doctoral Advisor:	Manuel Blum
Known For:	Results in computational complexity theory
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

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. He joined the faculty of UCSD in 1989,^[4] having been a postdoc there from 1989 to 1991.^[3]

Contributions

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

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

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
• 2003 Best Paper Award at the Symposium on Theory of Computing
• named a 2004 Guggenheim fellow for work on "heuristics, proof complexity, and algorithmic techniques"

External links

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

Notes and References

1. Web site: Russell Impagliazzo - The Mathematics Genealogy Project. 2021-08-30. mathgenealogy.org.
2. Web site: Russell Impagliazzo's. 2021-08-30. cseweb.ucsd.edu.
3. Web site: Russell Impagliazzo Simons Institute for the Theory of Computing. 2021-08-30. simons.berkeley.edu.
4. Web site: Faculty Profile Jacobs School of Engineering . 2021-08-30 . jacobsschool.ucsd.edu.
5. HÅstad. Johan. Impagliazzo. Russell. Levin. Leonid A.. Luby. Michael. 1999. A Pseudorandom Generator from any One-way Function. SIAM Journal on Computing. 28. 4. 1364–1396. 10.1137/S0097539793244708. 0097-5397.
6. Impagliazzo. Russell. Proceedings of IEEE 36th Annual Foundations of Computer Science . 1995. Hard-core distributions for somewhat hard problems. https://ieeexplore.ieee.org/document/492584. Proceedings of IEEE 36th Annual Foundations of Computer Science. 538–545. 10.1109/SFCS.1995.492584. 0-8186-7183-1. 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. en. s3-73. 1. 1–26. 10.1112/plms/s3-73.1.1. 1460-244X.
8. Kabanets. Valentine. Impagliazzo. Russell. 2004-12-01. Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds. Computational Complexity. en. 13. 1. 1–46. 10.1007/s00037-004-0182-6. 12451799. 1420-8954.
9. Book: Impagliazzo. Russell. Wigderson. Avi. Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 . P = BPP if E requires exponential circuits . 1997-05-04. https://doi.org/10.1145/258533.258590. El Paso, Texas, USA. Association for Computing Machinery. 220–229. 10.1145/258533.258590. 978-0-89791-888-6. 18921599.
10. Impagliazzo. Russell. 2003-04-28. Hardness as randomness: a survey of universal derandomization. cs/0304040.
11. Carmosino. Marco L.. Impagliazzo. Russell. Kabanets. Valentine. Kolokolova. Antonina. 2015. Garg. Naveen. Jansen. Klaus. Rao. Anup. Rolim. José D. P.. 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. 10.4230/LIPIcs.APPROX-RANDOM.2015.645. free . 978-3-939897-89-7.
12. Book: Barak. B.. Impagliazzo. R.. Wigderson. A.. 45th Annual IEEE Symposium on Foundations of Computer Science . Extracting Randomness Using Few Independent Sources . 2004. https://ieeexplore.ieee.org/document/1366258. 384–393. 10.1109/FOCS.2004.29. 0-7695-2228-9. 7063583.
13. 2001-03-01. On the Complexity of k-SAT. Journal of Computer and System Sciences. en. 62. 2. 367–375. 10.1006/jcss.2000.1727. 0022-0000. Impagliazzo. Russell. Paturi. Ramamohan. free.
14. Lokshtanov. Daniel. Marx. Dániel. Saurabh. Saket. October 2011. Lower Bounds based on the Exponential Time Hypothesis. Bulletin of the EATCS. 41–71. 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. 10th International Symposium on Parameterized and Exact Computation. 17–29. 10.4230/LIPIcs.IPEC.2015.17. free .
16. Web site: Impagliazzo . Russell . A Personal View of Average-Case Complexity. April 17, 1995.
17. Web site: Klarreich . Erica . April 18, 2022 . Which Computational Universe Do We Live In? . Quanta.