Difficulté d'approximation [d'après Khot, Kindler, Mossel, O'Donnell,...]

Pansu, Pierre

Séminaire Bourbaki volume 2011/2012 exposés 1043-1058, Astérisque, no. 352 (2013), Exposé no. 1045, 38 p.

MR Zbl

@incollection{AST_2013__352__83_0,
     author = {Pansu, Pierre},
     title = {Difficult\'e d'approximation [d'apr\`es {Khot,} {Kindler,} {Mossel,} {O'Donnell,...]}},
     booktitle = {S\'eminaire Bourbaki volume 2011/2012 expos\'es 1043-1058},
     series = {Ast\'erisque},
     note = {talk:1045},
     pages = {83--120},
     publisher = {Soci\'et\'e math\'ematique de France},
     number = {352},
     year = {2013},
     mrnumber = {3087343},
     zbl = {06295886},
     language = {fr},
     url = {http://archive.numdam.org/item/AST_2013__352__83_0/}
}

TY  - CHAP
AU  - Pansu, Pierre
TI  - Difficulté d'approximation [d'après Khot, Kindler, Mossel, O'Donnell,...]
BT  - Séminaire Bourbaki volume 2011/2012 exposés 1043-1058
AU  - Collectif
T3  - Astérisque
N1  - talk:1045
PY  - 2013
SP  - 83
EP  - 120
IS  - 352
PB  - Société mathématique de France
UR  - http://archive.numdam.org/item/AST_2013__352__83_0/
LA  - fr
ID  - AST_2013__352__83_0
ER  -

%0 Book Section
%A Pansu, Pierre
%T Difficulté d'approximation [d'après Khot, Kindler, Mossel, O'Donnell,...]
%B Séminaire Bourbaki volume 2011/2012 exposés 1043-1058
%A Collectif
%S Astérisque
%Z talk:1045
%D 2013
%P 83-120
%N 352
%I Société mathématique de France
%U http://archive.numdam.org/item/AST_2013__352__83_0/
%G fr
%F AST_2013__352__83_0

Pansu, Pierre. Difficulté d'approximation [d'après Khot, Kindler, Mossel, O'Donnell,...], dans Séminaire Bourbaki volume 2011/2012 exposés 1043-1058, Astérisque, no. 352 (2013), Exposé no. 1045, 38 p. http://archive.numdam.org/item/AST_2013__352__83_0/

Bibliographie
Cité par

[1] N. Alon & A. Naor - Approximating the cut-norm via Grothendieck's inequality, SIAM J. Comput. 35 (2006), n° 4, p. 787-803. | DOI | MR | Zbl

[2] L. Ambrosio, B. Kleiner & E. Le Donne - Rectifiability of sets of finite perimeter in Carnot groups : existence of a tangent hyperplane, J. Geom. Anal. 19 (2009), n° 3, p. 509-540. | DOI | MR | Zbl

[3] C. Ambühl, M. Mastrolilli & O. Svensson - Inapproximability results for sparsest cut, optimal linear arrangement, and precedence constrained scheduling, in 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS) Providence, 2007, p. 329-337. | DOI

[4] S. Arora, B. Barak & D. Steurer - Subexponential algorithms for unique games and related problems, in 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), Las Vegas, 2010, p. 563-572. | MR

[5] S. Arora, E. Hazan & S. Kale - $O (\sqrt{log n})$ approximation to sparsest cut in $\tilde{O} (n^{2})$ time, SIAM J. Comput 39 (2010), n° 5, p. 1748-1771. | DOI | MR | Zbl

[6] S. Arora, J. R. Lee & A. Naor - Euclidean distortion and the sparsest cut, J. Amer. Math. Soc. 21 (2008), n° 1, p. 1-21. | DOI | MR | Zbl

[7] S. Arora, C. Lund, R. Motwani, M. Sudan & M. Szegedy - Proof verification and the hardness of approximation problems, J. ACM 45 (1998), n° 3, p. 501-555. | DOI | MR | Zbl

[8] S. Arora & S. Safra - Probabilistic checking of proofs : a new characterization of NP, J. ACM 45 (1998), n° 1, p. 70-122. | DOI | MR | Zbl

[9] P. Assouad - Espaces métriques, plongements, facteurs, thèse de doctorat, Université Paris XI, Orsay, 1977, Publications Mathématiques d'Orsay, No. 223-7769. | MR | Zbl

[10] T. Austin, A. Naor & R. Tessera - Sharp quantitative nonembeddability of the Heisenberg group into superreflexive Banach spaces, prépublication arXiv: 1007.4238. | DOI | MR | Zbl

[11] M. Ben Or & N. Linial - Collective coin flipping, robust voting games and minima of Banzhaf values, in 26th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Portland, 1985, p. 408-416.

[12] I. Benjamini, G. Kalai & O. Schramm - Noise sensitivity of Boolean functions and applications to percolation, Publ. Math. I.H.É.S. (1999), n° 90, p. 5-43. | DOI | EuDML | Numdam | MR | Zbl

[13] A. Bonami - Étude des coefficients de Fourier des fonctions de $L^{p} (G)$ , Ann. Inst. Fourier (Grenoble) 20 (1970), n° fasc. 2, p. 335-402. | DOI | EuDML | Numdam | MR | Zbl

[14] C. Borell - Geometric bounds on the Ornstein-Uhlenbeck velocity process, Z. Wahrsch. Verw. Gebiete 70 (1985), n° 1, p. 1-13. | DOI | MR | Zbl

[15] J. Bourgain - On Lipschitz embedding of finite metric spaces in Hilbert space, Israel J. Math. 52 (1985), nos 1-2, p. 46-52. | DOI | MR | Zbl

[16] M. Braverman, K. Makarychev, Y. Makarychev & A. Naor - The Grothendieck constant is strictly smaller than Krivine's bound, in 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), Palm Springs, 2011, p. 408-416. | MR | Zbl

[17] J. Bretagnolle, D. Dacunha-Castelle & J.-L. Krivine - Lois stables et espaces $L^{p}$ , Ann. Inst. H. Poincaré Sect. B (N.S.) 2 (1965/1966), p. 231-259. | EuDML | Numdam | MR | Zbl

[18] M. Charikar, K. Makarychev & Y. Makarychev - On the advantage over random for maximum acyclic subgraph, in 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Providence, 2007, p. 625-633. | DOI

[19] S. Chawla, R. Krauthgamer, R. Kumar, Y. Rabani & D. Sivakumar - On the hardness of approximating multicut and sparsest-cut, Comput. Complexity 15 (2006), n° 2, p. 94-114. | DOI | MR | Zbl

[20] B. Chazelle - The PCP theorem [after Arora, Lund, Motwani, Safra, Sudan, Szegedy], Séminaire Bourbaki, vol. 2001/2002, exp. n° 895, Astérisque 290 (2003), p. 19-36. | EuDML | Numdam | MR | Zbl

[21] J. Cheeger & B. Kleiner - On the differentiability of Lipschitz maps from metric measure spaces to Banach spaces, in Inspired by S. S. Chern, Nankai Tracts Math., vol. 11, World Sci. Publ., Hackensack, NJ, 2006, p. 129-152. | MR | Zbl

[22] J. Cheeger & B. Kleiner, Differentiating maps into $L^{1}$ , and the geometry of BV functions, Ann. of Math. 171 (2010), n° 2, p. 1347-1385. | DOI | MR | Zbl

[23] J. Cheeger & B. Kleiner, Metric differentiation, monotonicity and maps to $L^{1}$ , Invent. Math. 182 (2010), n° 2, p. 335-370. | DOI | MR | Zbl

[24] J. Cheeger, B. Kleiner & A. Naor - A ${(log n)}^{Ω (1)}$ integrality gap for the sparsest cut SDP, in 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Atlanta, 2009, p. 555-564. | DOI | MR | Zbl

[25] M. Chlamtac, K. Makarychev & Y. Makarychev - How to play unique games using embeddings, in 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Berkeley, 2006, p. 687-696.

[26] M. M. Deza & M. Laurent - Geometry of cuts and metrics, Algorithms and Combinatorics, vol. 15, Springer, 1997. | MR | Zbl

[27] I. Dinur - Probabilistically checkable proofs, in Proceedings of the International Congress of Mathematicians, ICM, Hyderabad, 2010. | Zbl

[28] I. Dinur & P. Harsha - Composition of low-error $2$ -query PCPs using decodable PCPs, in 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Atlanta, 2009, p. 472-481. | DOI | MR | Zbl

[29] A. Ehrhard - Symétrisation dans l'espace de Gauss, Math. Scand. 53 (1983), n° 2, p. 281-301. | DOI | EuDML | MR | Zbl

[30] P. Enflo - On the nonexistence of uniform homeomorphisms between $L_{p}$ -spaces, Ark. Mat 8 (1969), p. 103-105. | DOI | MR | Zbl

[31] U. Feige & G. Schechtman - On the optimality of the random hyperplane rounding technique for MAX CUT, Random Structures Algorithms 20 (2002), n° 3, p. 403-440. | DOI | MR | Zbl

[32] B. Franchi, R. Serapioni & F. Serra Cassano - On the structure of finite perimeter sets in step $2$ Carnot groups, J. Geom. Anal. 13 (2003), n° 3, p. 421-466. | DOI | MR | Zbl

[33] M. X. Goemans - Semidefinite programming in combinatorial optimization, Math. Programming 79 (1997), nos 1-3, Ser. B, p. 143-161. | DOI | MR | Zbl

[34] M. X. Goemans & D. P. Williamson - Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM 42 (1995), n° 6, p. 1115-1145. | DOI | MR | Zbl

[35] A. Grothendieck - Résumé de la théorie métrique des produits tensoriels topologiques, Bol. Soc. Mat. São Paulo 8 (1953), p. 1-79. | MR | Zbl

[36] V. Guruswami, R. Manokaran & P. Raghavendra - Beating the random ordering is hard : Inapproximability of maximum acyclic subgraph, in 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Philadelphia, 2008, p. 573-582.

[37] V. Guruswami, P. Raghavendra, R. Saket & Y. Wu - Bypassing UGC from some optimal geometric inapproximability results, Electr. Colloq. Comput. Compl. 17 (2010), p. 177.

[38] J. Håstad - Some optimal inapproximability results, J. ACM 48 (2001), n° 4, p. 798-859. | DOI | MR | Zbl

[39] S. Kakutani - Mean ergodic theorem in abstract $(L)$ -spaces, Proc. Imp. Acad., Tokyo 15 (1939), p. 121-123. | DOI | JFM | MR | Zbl

[40] S. Khot - On the power of unique $2$ -prover $1$ -round games, in Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, ACM, 2002, p. 767-775. | DOI | MR | Zbl

[41] S. Khot, Inapproximability of $N P$ -complete problems, discrete Fourier analysis, and geometry, in Proceedings of the International Congress of Mathematicians. Volume IV, Hindustan Book Agency, 2010, p. 2676-2697. | MR | Zbl

[42] S. Khot, On the unique games conjecture, in 25th Annual IEEE Conference on Computational Complexity-CCC 2010, 2010, p. 99-121. | DOI | MR

[43] S. Khot, G. Kindler, E. Mossel & R. O'Donnell - Optimal inapproximability results for MAX-CUT and other $2$ -variable CSPs ?, SIAM J. Comput. 37 (2007), n° 1, p. 319-357. | DOI | MR | Zbl

[44] S. Khot & A. Naor - Grothendieck-type inequalities in combinatorial optimization, Comm. Pure Appl. Math. 65 (2012), n° 7, p. 992-1035. | DOI | MR | Zbl

[45] S. Khot & M. Safra - A two prover one round game with strong soundness, in 52nd Annual IEEE Symposium on Foundations of Computer Science FOCS, Palm Springs, 2011, p. 648-657. | MR | Zbl

[46] S. Khot & N. Vishnoi - The unique games conjecture, integrality gap for cut problems and the embeddability of negative type metrics into $l_{1}$ , in 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Pittsburgh, 2005, p. 53-62. | DOI

[47] G. Kindler - Dictatorship testing and hardness of approximation, notes d'un cours donné à l'Institut Henri Poincaré, en février 2011, http://metric2011.wordpress.corn/.

[48] G. Kindler, A. Naor & G. Schechtman - The UGC hardness threshold of the $L_{p}$ Grothendieck problem, Math. Oper. Res. 35 (2010), n° 2, p. 267-283. | DOI | MR | Zbl

[49] J.-L. Krivine - Constantes de Grothendieck et fonctions de type positif sur les sphères, Adv. in Math. 31 (1979), n° 1, p. 16-30. | DOI | MR | Zbl

[50] J. B. Lasserre - Moments, positive polynomials and their applications, Imperial College Press Optimization Series, vol. 1, Imperial College Press, 2010. | MR | Zbl

[51] M. Laurent - Semidefinite relaxations for max-cut, in The sharpest cut, MPS/SIAM Ser. Optim., SIAM, 2004, p. 257-290. | MR | Zbl

[52] J. R. Lee & A. Naor - $L_{p}$ metrics on the Heisenberg group and the Goemans-Linial conjecture, in 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Berkeley, 2006, p. 99-108.

[53] N. Linial - Finite metric-spaces-combinatorics, geometry and algorithms, in Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002), Higher Ed. Press, 2002, p. 573-586. | MR | Zbl

[54] N. Linial, E. London & Y. Rabinovich - The geometry of graphs and some of its algorithmic applications, Combinatorica 15 (1995), n° 2, p. 215-245. | DOI | MR | Zbl

[55] L. Lovász - On the Shannon capacity of a graph, IEEE Trans. Inform. Theory 25 (1979), n° 1, p. 1-7. | DOI | MR | Zbl

[56] L. Lovász & A. Schrijver - Cones of matrices and set-functions and $0 - 1$ optimization, SIAM J. Optim. 1 (1991), n° 2, p. 166-190. | DOI | MR | Zbl

[57] G. A. Margulis - Probabilistic characteristics of graphs with large connectivity, Problemy Peredači Informacii 10 (1974), n° 2, p. 101-108. | MR | Zbl

[58] D. Moshkovitz & R. Raz - Sub-constant error probabilistically checkable proof of almost-linear size, Comput. Complexity 19 (2010), n° 3, p. 367-422. | DOI | MR | Zbl

[59] E. Mossel, R. O'Donnell & K. Oleszkiewicz - Noise stability of functions with low influences : invariance and optimality, Ann. of Math. 171 (2010), n° 1, p. 295-341. | DOI | MR | Zbl

[60] A. Naor & G. Schechtman - An approximation scheme for quadratic form maximization on convex bodies, manuscrit, 2009.

[61] A. Nemirovski - Advances in convex optimization : conic programming, in International Congress of Mathematicians. Vol. I, Eur. Math. Soc, Zürich, 2007, p. 413-444. | MR | Zbl

[62] Y. Nesterov & A. Nemirovskii - Interior-point polynomial algorithms in convex programming, SIAM Studies in Applied Mathematics, vol. 13, Society for Industrial and Applied Mathematics (SIAM), 1994. | MR | Zbl

[63] A. Newman - Approximating the maximum acyclic subgraph, thèse, MIT, 2000.

[64] P. Pansu - Métriques de Carnot-Carathéodory et quasiisométries des espaces symétriques de rang un, Ann. of Math. 129 (1989), n° 1, p. 1-60. | DOI | MR | Zbl

[65] M. Putinar - Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J. 42 (1993), n° 3, p. 969-984. | DOI | MR | Zbl

[66] P. Raghavendra - Optimal algorithms and inapproximability results for every CSP? [extended abstract], in STOC'08, ACM, 2008, p. 245-254. | MR | Zbl

[67] P. Raghavendra & D. Steurer - Graph expansion and the unique games conjecture, in STOCK'10-Proceedings of the 2010 ACM International Symposium on Theory of Computing, ACM, 2010, p. 755-764. | MR | Zbl

[68] R. Raz - A parallel repetition theorem, SIAM J. Comput. 27 (1998), n° 3, p. 763-803. | DOI | MR | Zbl

[69] R. Raz, $P \neq N P$ , propositional proof complexity, and resolution lower bounds for the weak pigeonhole principle, in Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002), Higher Ed. Press, 2002, p. 685-693. | MR | Zbl

[70] V. I. Rotar' - Limit theorems for polylinear forms, J. Multivariate Anal. 9 (1979), n° 4, p. 511-530. | DOI | MR | Zbl

[71] L. Russo - An approximate zero-one law, Z. Wahrsch. Verw. Gebiete 61 (1982), n° 1, p. 129-139. | DOI | MR | Zbl

[72] S. Semmes - On the nonexistence of bi-Lipschitz parameterizations and geometric problems about $A_{\infty}$ -weights, Rev. Mat. Iberoamericana 12 (1996), n° 2, p. 337-410. | DOI | EuDML | MR | Zbl

[73] H. D. Sherali & W. P. Adams - A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM J. Discrete Math. 3 (1990), n° 3, p. 411-430. | DOI | MR | Zbl