Russell Impagliazzo
Russell Graham Impagliazzo (né le à 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].
| Naissance | |
|---|---|
| Nationalité | |
| Formation | |
| Activités |
| A travaillé pour | |
|---|---|
| Directeur de thèse | |
| Distinctions |
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'identité 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 )
- (en) « UC San Diego Engineering Professor Wins Guggenheim Fellowship », sur ucsdnews.ucsd.edu (consulté le )
- (en) « Faculty Awards | Computer Science and Engineering », sur cse.ucsd.edu (consulté le )
- (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, no 4,‎ , p. 1364–1396 (ISSN 0097-5397 et 1095-7111, DOI 10.1137/s0097539793244708, lire en ligne, consulté le )
- (en) « SIAM Outstanding Paper Prizes », sur www.siam.org (consulté le )
- (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,‎ , p. 2–12 (DOI 10.1109/CCC.2001.933865, lire en ligne, consulté le )
- (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,‎ , p. 355–364 (ISBN 1581136749, DOI 10.1145/780542.780595, lire en ligne, consulté le )
- « ACM SIGACT: Prizes: Best Paper », sur www.sigact.org (consulté le )
- (en) Russell Impagliazzo et Steven Rudich, « Limits on the Provable Consequences of One-way Permutations », dans Advances in Cryptology — CRYPTO’ 88, Springer New York, (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),‎ , p. 237–240 (DOI 10.1109/CCC.1999.766282, lire en ligne, consulté le )
- (en) R. Impagliazzo, « A personal view of average-case complexity », Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference,‎ , p. 134–147 (DOI 10.1109/SCT.1995.514853, lire en ligne, consulté le )