Uriel Feige
Pour les articles homonymes, voir Feige.
| Naissance | |
|---|---|
| Nationalité | |
| Formation | |
| Activités |
| Directeur de thèse | |
|---|---|
| Distinction |
Prix Gödel () |
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 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
[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]- (en) « Uriel Feige », sur le site du Mathematics Genealogy Project.
- Feige et al., « Interactive proofs », 1996.
- Feige-Fiat-Shamir, 1988.
Liens externes
[modifier | modifier le code]- Page personnelle à l'Institut Weizmann.
- Ressources relatives à la recherche :
