| 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 is a professor of computer science at the University of California, San Diego, specializing in computational complexity theory.
Education
Impagliazzo received a BA in mathematics from Wesleyan University. 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, having been a postdoc there from 1989 to 1991.
Contributions
Impagliazzo's contributions to complexity theory include:
- the construction of a pseudorandom number generator from any one-way function,
- his proof of Yao's XOR lemma via "hard core sets",
- his proof of the exponential size lower bound for constant-depth Hilbert proofs of the pigeonhole principle,
- his work on connections between computational hardness and de-randomization,
- and his work on the construction of multi-source seedless extractors.
- stating the exponential time hypothesis that 3-SAT cannot be solved in subexponential time in the number of variables, This hypothesis is used to deduce lower bounds on algorithms in computer science.
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.
- 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.
Awards
Impagliazzo has received the following awards:
- Best Paper Award from the Computational Complexity Conference
- 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"
References
- ^ "Russell Impagliazzo - The Mathematics Genealogy Project". mathgenealogy.org. Retrieved 2021-08-30.
- "Russell Impagliazzo's". cseweb.ucsd.edu. Retrieved 2021-08-30.
- ^ "Russell Impagliazzo | Simons Institute for the Theory of Computing". simons.berkeley.edu. Retrieved 2021-08-30.
- ^ "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
| Nerode Prize laureates | |
|---|---|
|