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.
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 cryptographieEn anglais : Pseudo-random Generators for Probablistic Algorithms and for Cryptography. », 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), Sloan Fellow, Fulbright Fellow,Young Investigator de la National Science Foundation, et lauréat du prix IPEC Nerode en 2013.
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, que le SIAM a récompensé de l'Outstanding Paper Award en 2003 ; la preuve (entre autres résultats) qu'aucune dérandomisation de MA n'est possible à moins que NEXP ne contienne une fonction booléenne difficileC'est-à-dire, une fonction qui ne peut être décrite qu'au moyen d'un circuit booléen de taille superlinéaire., récompensé par l'IEEE du Best Conference Paper Award ; la preuve qu'une dérandomisation pour le est équivalente à une preuve de bornes inférieures de complexité dans NEXP, récompensé par le Best Paper Award de l'ACM en 2003; la première technique de séparation en boîte noire ; l' ; les « cinq mondes » de la complexité moyenne.
Notes et références
Notes
Références
Liens externes
Catégorie:Boursier Guggenheim Catégorie:Informaticien américain Catégorie:Cryptologue américain Catégorie:Naissance à Providence (Rhode Island) Catégorie:Naissance en mai 1963