Russell Impagliazzo

Russell Graham Impagliazzo (Providence, 29 maggio 1963) è un informatico statunitense, professore di informatica presso l'Università della California, San Diego, specializzato in teoria della complessità computazionale.

Ha conseguito la laurea in matematica presso la Wesleyan University e il dottorato presso l'Università della California, Berkeley, nel 1992.

Contributi scientifici

I contributi di Impagliazzo alla teoria della complessità computazionale includono:

la costruzione di un generatore di numeri pseudocasuali da qualsiasi funzione unidirezionale;
la dimostrazione del lemma XOR di Yao tramite "insiemi hard core";
la dimostrazione del limite inferiore di dimensione esponenziale per le dimostrazioni di Hilbert a profondità costante del principio dei cassetti;
un lavoro sulle connessioni tra difficoltà computazionale e de-randomizzazione;
un lavoro sulla costruzione di estrattori senza semi multi-sorgente;
l'ipotesi del tempo esponenziale secondo cui 3-SAT non può essere risolto in tempo subesponenziale nel numero di variabili, ipotesi utilizzata per dedurre limiti inferiori sugli algoritmi.

I cinque mondi della teoria della complessità

Impagliazzo è noto per aver proposto i “cinque mondi” della teoria della complessità computazionale, che riflettono i possibili stati del mondo reale rispetto al problema P contro NP.

Algoritmica: P = NP. Ogni problema in NP si risolve in tempo polinomiale e quindi la crittografia basata sulla difficoltà computazionale non è, in linea di principio, sicura (rimangono sicure altre crittografie come il one-time pad o la crittografia quantistica);
Euristica: P ≠ NP, ma i problemi NP sono mediamente trattabili in tempo polinomiale;
Pessiland: P ≠ NP e i problemi NP sono mediamente difficili, ma non esistono funzioni unidirezionali (difficile da invertire), quindi esistono molti problemi algoritmicamente difficili, ma non si possono sfruttare per la crittografia;
Minicrypt: P ≠ NP, i problemi NP sono mediamente difficili ed esistono funzioni unidirezionali. Sono quindi possibili forme di cifratura simmetrica sicure, ma la crittografia a chiave pubblica riamane comunque insicura;
Crittomania: P ≠ NP, i problemi NP sono mediamente difficili, esistono funzioni unidirezionali e, in linea di principio, è possibile ottenere algoritmi di crittografia a chiave pubblica sicuri.

Al momento non è possibile stabilire a quale di questi mondi appartiene il mondo in cui viviamo, questione che rimane alla base della teoria della complessità computazionale e della crittografia.

Riconoscimenti

Impagliazzo ha ricevuto i seguenti premi:

Premio per il miglior articolo della conferenza sulla complessità computazionale;
Premio per il miglior articolo del 2003 dalla Society for Industrial and Applied Mathematics;
Premio per il miglior articolo del 2003 al Simposio sulla teoria dell'informatica;
nominato borsista Guggenheim nel 2004 per il lavoro su "euristiche, complessità delle dimostrazioni e tecniche algoritmiche".

Note

↑ (EN) Russell Impagliazzo: Birthday, Age, and Zodiac, su Happy Happy Birthday. URL consultato il 23 ottobre 2026.
↑ Russell Impagliazzo's, su cseweb.ucsd.edu. URL consultato il 30 agosto 2021.
1 2 Russell Impagliazzo | Simons Institute for the Theory of Computing, su simons.berkeley.edu. URL consultato il 30 agosto 2021.
↑ HÅstad, A Pseudorandom Generator from any One-way Function (PDF), in SIAM Journal on Computing, vol. 28, 1999, pp. 1364–1396, DOI:10.1137/S0097539793244708, ISSN 0097-5397 (WC · ACNP).
↑ DOI:10.1109/SFCS.1995.492584, ISBN 0-8186-7183-1.
↑ (EN) Beame, Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs, in Proceedings of the London Mathematical Society, s3-73, 1996, pp. 1–26, DOI:10.1112/plms/s3-73.1.1, ISSN 1460-244X (WC · ACNP).
↑ (EN) Kabanets, Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds, in Computational Complexity, vol. 13, 1º dicembre 2004, pp. 1–46, DOI:10.1007/s00037-004-0182-6, ISSN 1420-8954 (WC · ACNP).
↑ Russell Impagliazzo e Avi Wigderson, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97, Association for Computing Machinery, 4 maggio 1997, pp. 220–229, DOI:10.1145/258533.258590, ISBN 978-0-89791-888-6.
↑ Carmosino, Tighter Connections between Derandomization and Circuit Lower Bounds, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015), Leibniz International Proceedings in Informatics (LIPIcs), vol. 40, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015, pp. 645–658, DOI:10.4230/LIPIcs.APPROX-RANDOM.2015.645, ISBN 978-3-939897-89-7.
↑ B. Barak, R. Impagliazzo e A. Wigderson, 45th Annual IEEE Symposium on Foundations of Computer Science, 2004, pp. 384–393, DOI:10.1109/FOCS.2004.29, ISBN 0-7695-2228-9.
↑ (EN) Impagliazzo, On the Complexity of k-SAT, in Journal of Computer and System Sciences, vol. 62, 1º marzo 2001, pp. 367–375, DOI:10.1006/jcss.2000.1727, ISSN 0022-0000 (WC · ACNP).
↑ Lokshtanov, Lower Bounds based on the Exponential Time Hypothesis, in Bulletin of the EATCS, October 2011, pp. 41–71.
↑ DOI:10.4230/LIPIcs.IPEC.2015.17, https://drops.dagstuhl.de/opus/volltexte/2015/5568/pdf/5.pdf.
↑ Impagliazzo, A Personal View of Average-Case Complexity (ps), su cseweb.ucsd.edu, April 17, 1995.
↑ Klarreich, Which Computational Universe Do We Live In?, su Quanta, April 18, 2022.
1 2 3 Faculty Profile | Jacobs School of Engineering, su jacobsschool.ucsd.edu. URL consultato il 30 agosto 2021.

Collegamenti esterni

(EN) Sito ufficiale, su cseweb.ucsd.edu.

(EN) Russell Impagliazzo, su Mathematics Genealogy Project, North Dakota State University.

Controllo di autorità	VIAF (EN) 105123019 · ISNI (EN) 0000 0003 7222 2529 · ORCID (EN) 0000-0003-3236-9796

Portale Biografie

Portale Informatica

[happyhappybirthday-1] (EN) Russell Impagliazzo: Birthday, Age, and Zodiac, su Happy Happy Birthday. URL consultato il 23 ottobre 2026.

[2] Russell Impagliazzo's, su cseweb.ucsd.edu. URL consultato il 30 agosto 2021.

[simons-3] 1 2 Russell Impagliazzo | Simons Institute for the Theory of Computing, su simons.berkeley.edu. URL consultato il 30 agosto 2021.

[4] HÅstad, A Pseudorandom Generator from any One-way Function (PDF), in SIAM Journal on Computing, vol. 28, 1999, pp. 1364–1396, DOI:10.1137/S0097539793244708, ISSN 0097-5397 (WC · ACNP).

[5] DOI:10.1109/SFCS.1995.492584, ISBN 0-8186-7183-1.

[6] (EN) Beame, Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs, in Proceedings of the London Mathematical Society, s3-73, 1996, pp. 1–26, DOI:10.1112/plms/s3-73.1.1, ISSN 1460-244X (WC · ACNP).

[7] (EN) Kabanets, Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds, in Computational Complexity, vol. 13, 1º dicembre 2004, pp. 1–46, DOI:10.1007/s00037-004-0182-6, ISSN 1420-8954 (WC · ACNP).

[8] Russell Impagliazzo e Avi Wigderson, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97, Association for Computing Machinery, 4 maggio 1997, pp. 220–229, DOI:10.1145/258533.258590, ISBN 978-0-89791-888-6.

[9] Carmosino, Tighter Connections between Derandomization and Circuit Lower Bounds, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015), Leibniz International Proceedings in Informatics (LIPIcs), vol. 40, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015, pp. 645–658, DOI:10.4230/LIPIcs.APPROX-RANDOM.2015.645, ISBN 978-3-939897-89-7.

[10] B. Barak, R. Impagliazzo e A. Wigderson, 45th Annual IEEE Symposium on Foundations of Computer Science, 2004, pp. 384–393, DOI:10.1109/FOCS.2004.29, ISBN 0-7695-2228-9.

[11] (EN) Impagliazzo, On the Complexity of k-SAT, in Journal of Computer and System Sciences, vol. 62, 1º marzo 2001, pp. 367–375, DOI:10.1006/jcss.2000.1727, ISSN 0022-0000 (WC · ACNP).

[12] Lokshtanov, Lower Bounds based on the Exponential Time Hypothesis, in Bulletin of the EATCS, October 2011, pp. 41–71.

[13] DOI:10.4230/LIPIcs.IPEC.2015.17, https://drops.dagstuhl.de/opus/volltexte/2015/5568/pdf/5.pdf.

[14] Impagliazzo, A Personal View of Average-Case Complexity (ps), su cseweb.ucsd.edu, April 17, 1995.

[15] Klarreich, Which Computational Universe Do We Live In?, su Quanta, April 18, 2022.

[:1-16] 1 2 3 Faculty Profile | Jacobs School of Engineering, su jacobsschool.ucsd.edu. URL consultato il 30 agosto 2021.