Uriel Feige

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Uriel Feige
une illustration sous licence libre serait bienvenue
Biographie
Naissance
Nationalité
Lieu de travail
Formation
Activités
Autres informations
Domaine
Sciences de l'information (en)Voir et modifier les données sur Wikidata
Directeur de thèse
Distinction

Uriel Feige (en hébreu : אוריאל פייגה, né en 1959) est un informaticien israélien. Ses recherches portent sur la théorie de la complexité, notamment les problèmes d'optimisation combinatoire NP-difficiles et la cryptographie. Il s'intéresse également aux marches aléatoires, aux algorithmes randomisés et à la théorie des jeux.

Parcours professionnel[modifier | modifier le code]

Feige fait des études d'informatique au Technion à partir de 1977, puis à l'Institut Weizmann à partir de 1985. Entre temps, il est de 1980 à 1985 ingénieur informaticien dans l'armée israélienne. En 1987, il obtient son diplôme de M. Sc. (« Interactive Proofs ») et un Ph. D. en 1990 à l'Institut Weizmann sous la direction d'Adi Shamir, avec une thèse intitulée « Alternative Models for Zero Knowledge Interactive Proofs »[1]. Il est chercheur postdoctoral à l'université de Princeton en 1990-1991 et en 1991-1992 au Thomas J. Watson Research Center (en) d'IBM. À partir de 1992 il est à l'Institut Weizmann, d'abord chercheur, puis chercheur sénior, ensuite professeur assistant et enfin, depuis 2003 professeur titulaire sur la chaire Lawrence G. Horowitz. Il y dirige, depuis 2007, le département d'informatique et de mathématiques appliquées. De 2004 à 2007, il fait partie du groupe théorique de Microsoft Research, et depuis 2009, il est consultant chez Microsoft Research. En 1998/99 il séjourne en année sabbatique au Compaq Systems Research Center à Palo Alto.

Prix et distinctions[modifier | modifier le code]

Pour son travail sur le théorème PCP et ses applications il est en 2001 récipiendaire, avec Shafi Goldwasser, László Lovász, Shmuel Safra et Mario Szegedy du prix Gödel[2]. En cryptographie, il applique en 1988 la preuve à divulgation nulle de connaissance au schéma d'identification appelé le schéma d'identification de Feige–Fiat–Shamir (en)[3]. En 2002, il est conférencier invité au Congrès international des mathématiciens in Pékin (titre de sa conférence : « Approximation thresholds for combinatorial optimization problems »).

Publications (sélection)[modifier | modifier le code]

  • Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra et Mario Szegedy, « Interactive proofs and the hardness of approximating cliques », Journal of the ACM, vol. 43, no 2,‎ , p. 268–292 (DOI 10.1145/226643.226652, lire en ligne).
  • Uriel Feige, Amos Fiat et Adi Shamir, « Zero-knowledge proofs of identity », Journal of Cryptology, vol. 1, no 2,‎ , p. 77–94 (DOI 10.1007/BF02351717).
  • Yehuda Afek, Yakov Babichenko, Uriel Feige, Eli Gafni, Nati Linial et Benny Sudakov, « Musical Chairs », SIAM J. Discrete Math., vol. 28, no 3,‎ , p. 1578-1600 (DOI 10.1137/12088478X)
  • Uriel Feige et Shlomo Jozeph, « Oblivious Algorithms for the Maximum Directed Cut Problem », Algorithmica, vol. 71, no 2,‎ , p. 409-428 (DOI 10.1007/s00453-013-9806-z)
  • David S. Johnson et Uriel Feige (éditeurs), Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA,, ACM, (ISBN 978-1-59593-631-8)

Notes et références[modifier | modifier le code]

Liens externes[modifier | modifier le code]