Russell Impagliazzo

Russell Impagliazzo
Biographie
Naissance
Voir et modifier les données sur Wikidata (61 ans)
ProvidenceVoir et modifier les données sur Wikidata
Nom dans la langue maternelle
Russell Graham ImpagliazzoVoir et modifier les données sur Wikidata
Nationalité
américaineVoir et modifier les données sur Wikidata
Formation
Activités
Informaticien, professeur d'université, cryptographeVoir et modifier les données sur Wikidata
Autres informations
A travaillé pour
Université de Californie à San Diego (depuis le )Voir et modifier les données sur Wikidata
Directeur de thèse
Manuel BlumVoir et modifier les données sur Wikidata
Site web
(en) cseweb.ucsd.edu//~russellVoir et modifier les données sur Wikidata
Distinctions
Bourse Guggenheim ()
Prix IPEC Nerode ()Voir et modifier les données sur Wikidata

modifier - modifier le code - modifier WikidataDocumentation du modèle

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].

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

  1. ↑ En anglais : Pseudo-random Generators for Probablistic Algorithms and for Cryptography.
  2. ↑ 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

  1. ↑ (en) « UCSD, Faculty Profiles: Russell Impagliazzo », sur jacobsschool.ucsd.edu (consulté le )
  2. ↑ (en) « UC San Diego Engineering Professor Wins Guggenheim Fellowship », sur ucsdnews.ucsd.edu (consulté le )
  3. ↑ (en) « Faculty Awards | Computer Science and Engineering », sur cse.ucsd.edu (consulté le )
  4. ↑ (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 )
  5. ↑ (en) « SIAM Outstanding Paper Prizes », sur www.siam.org (consulté le )
  6. ↑ (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 )
  7. ↑ (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 )
  8. ↑ « ACM SIGACT: Prizes: Best Paper », sur www.sigact.org (consulté le )
  9. ↑ (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
  10. ↑ (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 )
  11. ↑ (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 )

Liens externes

  • Notices d'autoritéVoir et modifier les données sur Wikidata :
    • VIAF
    • ISNI
    • Canada
  • icône décorative Portail de la cryptologie
  • icône décorative Portail de l’informatique