Groupe de lecture

Complexité Algorithmique

à l'ENS, 45 rue d'Ulm.

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é ;
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 ;
une mise en jambes en vue d'un groupe de lecture plus avancé, dirigé par Nicolas Schabanel (LIAFA), pour une lecture intégrale du livre ci-dessous.

Bibliographie : le livre à paraître de S. Arora et B. Barak, voir
http://www.cs.princeton.edu/theory/complexity/
spécialement, les chapitres 11 et 22.

Mardi 31 mars 2009, exceptionnellement à 18h, salle W (Toits du DMA)
P. Pansu Présentation du sujet, organisation Notes

Mardi 7 avril 2009, 17h30, salle R (couloir rouge, 2e sous-sol, accès par la cour Pasteur).
P. Pansu Codes linéaires

Page maintenue par Pierre Pansu

Mis à jour le 31 MARS 2009