DMA Web Site

Bannière DMA Site de l'ENS Site Paris Sciences et Lettres Site du CNRS Accueil

Reading group in computational complexity

Organizing institutions: ENS
Organised by: PANSU Pierre, professeur, pansu@dma.ens.fr, 0144322087
Usual location: ENS, en général en salle R

In the spring of 2009, we studied the PCP theorem from chapters 11 and 22 of Arora and Barak's new book Computational Complexity : A Modern Approach, and Chazelle's 2001 Bourbaki seminar. This led us to MAX-CUT, gadgets and Hastad's unconditional hardness of approximation bounds.
In the winter 2009-2010, we study UGC and its (sharp) consequences for MAX-CUT and other CSPs, using documents from a summer school organized by David Fisher, Netz Katz and James R. Lee (see James R. Lee's not a blog).
Later on, we shall continue reading Arora and Barak's book.

Website: http://www.dma.ens.fr/~pansu/glca/GLCA.html

Next sessions

No session

Past sessions

45 rue d'Ulm - F 75230 PARIS cedex 05 | phone : (33) 1 44 32 20 49 | fax : (33) 1 44 32 20 69

Site Map | Legal notice | | Website editor | Web site designed under SPIP