Russell Impagliazzo

Russell Graham Impagliazzo (Providence, 29 maggio 1963[1]) è un informatico e matematico statunitense, professore di informatica presso l'Università della California, San Diego, specializzato in teoria della complessità computazionale[2].
Ha conseguito la laurea in matematica presso la Wesleyan University[3] e il dottorato presso l'Università della California, Berkeley, nel 1992.
Contributi scientifici
[modifica | modifica wikitesto]I contributi di Impagliazzo alla teoria della complessità computazionale includono:
- la costruzione di un generatore di numeri pseudocasuali da qualsiasi funzione unidirezionale;[4]
- la dimostrazione del lemma XOR di Yao tramite "insiemi hard core";[5]
- la dimostrazione del limite inferiore di dimensione esponenziale per le dimostrazioni di Hilbert a profondità costante del principio dei cassetti;[6]
- un lavoro sulle connessioni tra difficoltà computazionale e de-randomizzazione;[7][8][9]
- un lavoro sulla costruzione di estrattori senza semi multi-sorgente;[10]
- l'ipotesi del tempo esponenziale secondo cui 3-SAT non può essere risolto in tempo subesponenziale nel numero di variabili,[11] ipotesi utilizzata per dedurre limiti inferiori sugli algoritmi.[12][13]
I cinque mondi della teoria della complessità
[modifica | modifica wikitesto]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.[14]
- 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.[15]
Riconoscimenti
[modifica | modifica wikitesto]Impagliazzo ha ricevuto i seguenti premi:
- Premio per il miglior articolo della conferenza sulla complessità computazionale;[3]
- Premio per il miglior articolo del 2003 dalla Society for Industrial and Applied Mathematics;[16]
- Premio per il miglior articolo del 2003 al Simposio sulla teoria dell'informatica;[16]
- nominato borsista Guggenheim nel 2004 per il lavoro su "euristiche, complessità delle dimostrazioni e tecniche algoritmiche".[16]
Note
[modifica | modifica wikitesto]- ↑ (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.
- ↑ R. Impagliazzo, Hard-core distributions for somewhat hard problems, IEEE Comput. Soc. Press, pp. 538–545, DOI:10.1109/SFCS.1995.492584. URL consultato il 24 ottobre 2026.
- ↑ (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.
- ↑ (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.
- ↑ 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.
- ↑ Lokshtanov, Lower Bounds based on the Exponential Time Hypothesis, in Bulletin of the EATCS, October 2011, pp. 41–71.
- ↑ (EN) Virginia Vassilevska Williams, Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk), in LIPIcs, Volume 43, IPEC 2015, vol. 43, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 17–29, DOI:10.4230/LIPICS.IPEC.2015.17. URL consultato il 24 ottobre 2026.
- ↑ 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
[modifica | modifica wikitesto]- (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 |
|---|
- Informatici statunitensi del XX secolo
- Informatici statunitensi del XXI secolo
- Matematici statunitensi del XX secolo
- Matematici statunitensi del XXI secolo
- Nati nel 1963
- Nati il 29 maggio
- Nati a Providence
- Studenti dell'Università della California, Berkeley
- Professori dell'Università della California - San Diego