From Wikipedia, the free encyclopedia
American computer scientist
Russell Graham Impagliazzo
[1] is a professor of computer science at the
University of California, San Diego , specializing in
computational complexity theory.
[2]
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]
Impagliazzo's contributions to complexity theory include:
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]
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]
Impagliazzo has received the following awards:
^
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 .
Calabro,
Impagliazzo , Kabanets, Paturi, Zane (2013)
Bodlaender , Downey,
Fellows , Hermelin,
Fortnow , Santhanam (2014)
Demaine ,
Fomin ,
Hajiaghayi , Thilikos (2015)
Björklund (2016)
Fomin , Grandoni, Kratsch (2017)
Kratsch, Wahlström (2018)
Alon , Yuster,
Zwick (2019)