Optimalité de l’algorithme de Goemans-Williamson pour MAXCUT conditionnellement à UGC, d’après Khot, Kindler, Mossel et O’Donnell
ENS Salle RUGC + Majority is stablest => borne optimale d'inapproximabilité pour MAX-CUT
UGC + Majority is stablest => borne optimale d'inapproximabilité pour MAX-CUT
Preuve du principe d'invariance, version minimale utile pour Majority is Stablest
Premier exposé sur les travaux de Prasad Raghavendra
Par un argument de réarrangement, Borell prouve que les fonctions indicatrices de demi-espaces maximisent la stabilité parmi toutes les fonctions sur l'espace gaussien, à valeurs dans , de moyenne 1/2.
On explique, dans la généralité étudiée par Raghavendra, la réduction de UNIQUE VERTEX COVER a un problème de satisfaction de contraintes, en utilisant les tests de dictature décrits par Eric.
Pansu explique le théorème KKL, son interprétation isopérimétrique, et sa preuve. Graham en donne une application à une preuve moderne d'un résultat célèbre de Harris et Kesten.
On donne un aperçu du manuscrit récent qui produit une borne inférieure effective à la distorsion des plongements des boules du groupe de Heisenberg discret dans L^1.
En s'inspirant du livre Matousek et d'un survol qui constitue une mise à jour d'une partie de ce livre, Arnaud explique différents problèmes et résultats sur les plongements d'espaces métriques finis dans les L^p, et des L^p entre eux.
On donne un aperçu de la preuve
C'est le fameux théorème d'Assouad sur le plongement dans l'espace euclidien d'espaces de dimension d'Assouad finie.
On explique et on prouve le théorème de Dvoretsky sur les sections presque euclidiennes des espaces de Banach.
On termine la preuve