Uriel Feige
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.
| Naissance | |
|---|---|
| Nationalité | |
| Formation | |
| Activités |
| Directeur de thèse | |
|---|---|
| Distinction |
Prix Gödel () |
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
Liens externes
- Page personnelle à l'Institut Weizmann.
- Ressources relatives à la recherche :