Uriel Feige

Page d’aide sur l’homonymie

Pour les articles homonymes, voir Feige.

Uriel Feige
une illustration sous licence libre serait bienvenue
Biographie
Naissance
Nationalité
Formation
Activités
Autres informations
Directeur de thèse
Distinction
Prix Gödel ()Voir et modifier les données sur Wikidata

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

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

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 d'IBM. À partir de 1992 il est à l'Institut Weizmann, d'abord chercheur, puis chercheur senior, 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

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)

  • 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

  1. ↑ (en) « Uriel Feige », sur le site du Mathematics Genealogy Project.
  2. ↑ Feige et al., « Interactive proofs », 1996.
  3. ↑ Feige-Fiat-Shamir, 1988.

Liens externes

v · m
Lauréats du prix Gödel