Institutions organisatrices : ENS
Organisé par : PANSU Pierre, professeur, pansu@dma.ens.fr, 0144322087
Lieu habituel : ENS, en général en salle R
L’objet de ce groupe de lecture est
– une remise à niveau pour ceux qui ont suivi un cours élémentaire de complexité (P, NP) mais n’auront pas la chance de suivre un cours plus avancé ;
– au printemps 2009, une occasion de comprendre le théorème PCP et comment il entraîne la difficulté à résoudre, même de façon approchée, des problèmes classiques ;
– en 2009-2010, étudier une conjecture qui renforce le théorème PCP, la conjecture des jeux uniques (Unique Games Conjecture de S. Khot) et certaines de ses conséquences : conditionnellement à cette conjecture, on peut démontrer que certains algorithmes d’approximation polynômiaux sont optimaux ;
– une mise en jambes en vue d’un groupe de lecture plus avancé, dirigé par Nicolas Schabanel (LIAFA) à partir de mars 2010, pour une lecture intégrale du livre ci-dessous.
Bibliographie :
– Le livre de S. Arora et B. Barak, Computational Complexity : A Modern Approach, spécialement, les chapitres 11 et 22.
– Le séminaire Bourbaki de B. Chazelle, The PCP theorem [after Arora, Lund, Motwani, Safra, Sudan, Szegedy]. Séminaire Bourbaki. Vol. 2001/2002. Astérisque No. 290 (2003), Exp. No. 895, 19-36.
– Les documents issus de l’école d’été organisée en août 2009 par David Fisher, Netz Katz et James R. Lee, qu’on trouve à la page not a blog de James R. Lee.
Site internet : http://www.dma.ens.fr/~pansu/glca/GLCA.html