Difficulté d'approximation [d'après Khot, Kindler, Mossel, O'Donnell,...]
Séminaire Bourbaki volume 2011/2012 exposés 1043-1058, Astérisque, no. 352 (2013), Exposé no. 1045, 38 p.
Le texte intégral des articles récents est réservé aux abonnés de la revue. Consultez le site de la revue.
@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},
     author = {Collectif},
     series = {Ast\'erisque},
     note = {talk:1045},
     publisher = {Soci\'et\'e math\'ematique de France},
     number = {352},
     year = {2013},
     zbl = {06295886},
     mrnumber = {3087343},
     language = {fr},
     url = {archive.numdam.org/item/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/

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

[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. | Article | MR 2496564 | Zbl 1187.28008

[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. | Article

[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 3025231

[5] S. Arora, E. Hazan & S. Kale - O(logn) approximation to sparsest cut in O ˜(n 2 ) time, SIAM J. Comput 39 (2010), n° 5, p. 1748-1771. | Article | MR 2592032 | Zbl 1207.68441

[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. | Article | MR 2350049 | Zbl 1132.68070

[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. | Article | MR 1639346 | Zbl 1065.68570

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

[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 644642 | Zbl 0396.46035

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

[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. | Article | EuDML 104164 | Numdam | MR 1813223 | Zbl 0986.60002

[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. | Article | EuDML 74019 | Numdam | MR 283496 | Zbl 0195.42501

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

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

[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 2932721 | Zbl 1292.90243

[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 76861 | Numdam | MR 203757 | Zbl 0139.33501

[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. | Article

[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. | Article | MR 2243123 | Zbl 1132.68418

[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 110305 | Numdam | MR 2074049 | Zbl 1161.68475

[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 2313333 | Zbl 1139.58004

[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. | Article | MR 2630066 | Zbl 1194.22009

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

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

[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 1460488 | Zbl 0885.52001

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

[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. | Article | MR 2648428 | Zbl 1292.68083

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

[30] P. Enflo - On the nonexistence of uniform homeomorphisms between L p -spaces, Ark. Mat 8 (1969), p. 103-105. | Article | MR 271719 | Zbl 0196.14002

[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. | Article | MR 1900615 | Zbl 1005.90052

[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. | Article | MR 1984849 | Zbl 1064.49033

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

[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. | Article | MR 1412228 | Zbl 0885.68088

[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 94682 | Zbl 0074.32303

[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. | Article | MR 2144931 | Zbl 1127.68405

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

[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. | Article | MR 2121525 | Zbl 1192.68367

[41] S. Khot, Inapproximability of NP-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 2827989 | Zbl 1252.68143

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

[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. | Article | MR 2306295 | Zbl 1135.68019

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

[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 2933301 | Zbl 1292.68075

[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. | Article

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

[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. | Article | MR 2674720 | Zbl 1216.68340

[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. | Article | MR 521464 | Zbl 0413.46054

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

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

[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 1957562 | Zbl 0997.05019

[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. | Article | MR 1337355 | Zbl 0827.05021

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

[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. | Article | MR 1098425 | Zbl 0754.90039

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

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

[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. | Article | MR 2630040 | Zbl 1201.60031

[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 2334199 | Zbl 1135.90379

[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 1258086 | Zbl 0824.90112

[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. | Article | MR 979599 | Zbl 0678.53042

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

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

[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 2743325 | Zbl 1293.05373

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

[69] R. Raz, PNP, 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 1957570 | Zbl 1012.68081

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

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

[72] S. Semmes - On the nonexistence of bi-Lipschitz parameterizations and geometric problems about A -weights, Rev. Mat. Iberoamericana 12 (1996), n° 2, p. 337-410. | Article | EuDML 39505 | MR 1402671 | Zbl 0858.46017

[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. | Article | MR 1061981 | Zbl 0712.90050