Russell Impagliazzo

Russell Graham Impagliazzo (né le 29 mai 1963 à Providence, Rhode Island) est un informaticien et cryptologue américain, spécialisé en théorie de la complexité. Il est actuellement professeur à l'Université de Californie à San Diego[1].

Russell Impagliazzo

Biographie
Naissance	29 mai 1963 Providence
Nationalité	Américaine
Formation	Université de Californie à Berkeley
Activités	Informaticien, professeur d'université, ingénieur, cryptographe

Autres informations
A travaillé pour	Université de Californie à San Diego
Dir. de thèse	Manuel Blum
Distinctions	Bourse Guggenheim Prix IPEC Nerode (2013)

Biographie

Impagliazzo obtient son B.A. de l'Université Wesleyenne en 1984. Il soutient en 1992 sa thèse de doctorat en mathématiques à l'Université de Californie à Berkeley, avec pour titre « Générateurs pseudo-aléatoires pour les algorithmes probabilistes et la cryptographie[Note 1] », sous la direction de Manuel Blum. Il poursuit des études post-doctorales à l'Université de Toronto de 1989 à 1991 puis rejoint rejoint l'Université de Californie à San Diego où il a successivement occupé les postes d'assistant professor, associate professor, et professeur.

De 2007 à 2012, Impagliazzo a été professeur invité à l'Institute for Advanced Study de Princeton. Il est boursier Guggenheim (promotion 2004[2]), Sloan Fellow, Fulbright Fellow,Young Investigator de la National Science Foundation, et lauréat du prix IPEC Nerode en 2013[3].

Travaux

Parmi les résultats importants auxquels Impagliazzo a contribué, on compte :

la preuve que les fonctions à sens unique impliquent les générateurs pseudo-aléatoires[4], que le SIAM a récompensé de l'Outstanding Paper Award en 2003[5] ;
la preuve (entre autres résultats) qu'aucune dérandomisation de MA n'est possible à moins que NEXP ne contienne une fonction booléenne difficile[Note 2]^,[6], récompensé par l'IEEE du Best Conference Paper Award ;
la preuve qu'une dérandomisation pour le test d'indentité polynomiale (en) est équivalente à une preuve de bornes inférieures de complexité dans NEXP[7], récompensé par le Best Paper Award de l'ACM en 2003[8];
la première technique de séparation en boîte noire[9] ;
l'hypothèse du temps exponentiel (en) [10] ;
les « cinq mondes » de la complexité moyenne[11].

Notes et références

Notes

En anglais : Pseudo-random Generators for Probablistic Algorithms and for Cryptography.
C'est-à-dire, une fonction qui ne peut être décrite qu'au moyen d'un circuit booléen de taille superlinéaire.

Références

(en) « UCSD, Faculty Profiles: Russell Impagliazzo », sur jacobsschool.ucsd.edu (consulté le 19 septembre 2018)
(en) « UC San Diego Engineering Professor Wins Guggenheim Fellowship », sur ucsdnews.ucsd.edu (consulté le 19 septembre 2018)
(en) « Faculty Awards | Computer Science and Engineering », sur cse.ucsd.edu (consulté le 19 septembre 2018)
(en) Johan Håstad, Russell Impagliazzo, Leonid A. Levin et Michael Luby, « A Pseudorandom Generator from any One-way Function », SIAM Journal on Computing, vol. 28, n^o 4,‎ janvier 1999, p. 1364–1396 (ISSN 0097-5397 et 1095-7111, DOI 10.1137/s0097539793244708, lire en ligne, consulté le 19 septembre 2018)
(en) « SIAM Outstanding Paper Prizes », sur www.siam.org (consulté le 19 septembre 2018)
(en) R. Impagliazzo, V. Kabanets et A. Wigderson, « In search of an easy witness: exponential time vs. probabilistic polynomial time », Proceedings 16th Annual IEEE Conference on Computational Complexity,‎ juin 2001, p. 2–12 (DOI 10.1109/CCC.2001.933865, lire en ligne, consulté le 19 septembre 2018)
(en) Valentine Kabanets et Russell Impagliazzo, « Derandomizing polynomial identity tests means proving circuit lower bounds », STOC '03 Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, ACM,‎ 9 juin 2003, p. 355–364 (ISBN 1581136749, DOI 10.1145/780542.780595, lire en ligne, consulté le 19 septembre 2018)
« ACM SIGACT: Prizes: Best Paper », sur www.sigact.org (consulté le 19 septembre 2018)
(en) Russell Impagliazzo et Steven Rudich, « Limits on the Provable Consequences of One-way Permutations », dans Advances in Cryptology — CRYPTO’ 88, Springer New York, 21 août 1988 (ISBN 9780387971964, DOI 10.1007/0-387-34799-2_2, lire en ligne), p. 8–26
(en) R. Impagliazzo et R. Paturi, « Complexity of k-SAT », Proceedings. Fourteenth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference) (Cat.No.99CB36317),‎ mai 1999, p. 237–240 (DOI 10.1109/CCC.1999.766282, lire en ligne, consulté le 19 septembre 2018)
(en) R. Impagliazzo, « A personal view of average-case complexity », Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference,‎ juin 1995, p. 134–147 (DOI 10.1109/SCT.1995.514853, lire en ligne, consulté le 19 septembre 2018)

Liens externes

Notices d'autorité :

Portail de la cryptologie
Portail de l’informatique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[2] En anglais : Pseudo-random Generators for Probablistic Algorithms and for Cryptography.

[7] C'est-à-dire, une fonction qui ne peut être décrite qu'au moyen d'un circuit booléen de taille superlinéaire.

[1] (en) « UCSD, Faculty Profiles: Russell Impagliazzo », sur jacobsschool.ucsd.edu (consulté le 19 septembre 2018)

[3] (en) « UC San Diego Engineering Professor Wins Guggenheim Fellowship », sur ucsdnews.ucsd.edu (consulté le 19 septembre 2018)

[4] (en) « Faculty Awards | Computer Science and Engineering », sur cse.ucsd.edu (consulté le 19 septembre 2018)

[5] (en) Johan Håstad, Russell Impagliazzo, Leonid A. Levin et Michael Luby, « A Pseudorandom Generator from any One-way Function », SIAM Journal on Computing, vol. 28, n^o 4,‎ janvier 1999, p. 1364–1396 (ISSN 0097-5397 et 1095-7111, DOI 10.1137/s0097539793244708, lire en ligne, consulté le 19 septembre 2018)

[6] (en) « SIAM Outstanding Paper Prizes », sur www.siam.org (consulté le 19 septembre 2018)

[8] (en) R. Impagliazzo, V. Kabanets et A. Wigderson, « In search of an easy witness: exponential time vs. probabilistic polynomial time », Proceedings 16th Annual IEEE Conference on Computational Complexity,‎ juin 2001, p. 2–12 (DOI 10.1109/CCC.2001.933865, lire en ligne, consulté le 19 septembre 2018)

[9] (en) Valentine Kabanets et Russell Impagliazzo, « Derandomizing polynomial identity tests means proving circuit lower bounds », STOC '03 Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, ACM,‎ 9 juin 2003, p. 355–364 (ISBN 1581136749, DOI 10.1145/780542.780595, lire en ligne, consulté le 19 septembre 2018)

[10] « ACM SIGACT: Prizes: Best Paper », sur www.sigact.org (consulté le 19 septembre 2018)

[11] (en) Russell Impagliazzo et Steven Rudich, « Limits on the Provable Consequences of One-way Permutations », dans Advances in Cryptology — CRYPTO’ 88, Springer New York, 21 août 1988 (ISBN 9780387971964, DOI 10.1007/0-387-34799-2_2, lire en ligne), p. 8–26

[12] (en) R. Impagliazzo et R. Paturi, « Complexity of k-SAT », Proceedings. Fourteenth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference) (Cat.No.99CB36317),‎ mai 1999, p. 237–240 (DOI 10.1109/CCC.1999.766282, lire en ligne, consulté le 19 septembre 2018)

[13] (en) R. Impagliazzo, « A personal view of average-case complexity », Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference,‎ juin 1995, p. 134–147 (DOI 10.1109/SCT.1995.514853, lire en ligne, consulté le 19 septembre 2018)