Sparse quadratic forms and their geometric applications [following Baston, Spielman and Srivastava]
Séminaire Bourbaki Volume 2010/2011 Exposés 1027-1042. Avec table par noms d'auteurs de 1948/49 à 2009/10., Astérisque, no. 348 (2012), Exposé no. 1033, 29 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_2012__348__189_0,
     author = {Naor, Assaf},
     title = {Sparse quadratic forms and their geometric applications [following Baston, Spielman and Srivastava]},
     booktitle = {S\'eminaire Bourbaki Volume 2010/2011 Expos\'es 1027-1042. Avec table par noms d'auteurs de 1948/49 \`a 2009/10.},
     author = {Collectif},
     series = {Ast\'erisque},
     note = {talk:1033},
     publisher = {Soci\'et\'e math\'ematique de France},
     number = {348},
     year = {2012},
     zbl = {1264.15024},
     language = {en},
     url = {archive.numdam.org/item/AST_2012__348__189_0/}
}
Naor, Assaf. Sparse quadratic forms and their geometric applications [following Baston, Spielman and Srivastava], dans Séminaire Bourbaki Volume 2010/2011 Exposés 1027-1042. Avec table par noms d'auteurs de 1948/49 à 2009/10., Astérisque, no. 348 (2012), Exposé no. 1033, 29 p. http://archive.numdam.org/item/AST_2012__348__189_0/

[1] N. Alon - "Problems and results in extremal combinatorics. I", Discrete Math. 273 (2003), p. 31-53. | Article | Zbl 1033.05060

[2] A. Andoni, A. Naor & O. Neiman - "On isomorphic dimension reduction in 1 ", preprint, 2011.

[3] K. Ball - "Isometric embedding in l p -spaces", European J. Combin. 11 (1990), p. 305-311. | Article | Zbl 0712.46008

[4] K. Ball, "An elementary introduction to modern convex geometry", in Flavors of geometry, Math. Sci. Res. Inst. Publ., vol. 31, Cambridge Univ. Press, 1997, p. 1-58. | Zbl 0901.52002

[5] J. D. Batson, D. A. Spielman & N. Srivastava - "Twice-Ramanujan sparsifiers", in STOC'09 - Proceedings of the 2009 ACM International Symposium on Theory of Computing, ACM, 2009, p. 255-262. | Zbl 1304.05130

[6] A. A. Benczúr & D. R. Karger - "Approximating s-t minimum cuts in O ˜ ( n 2 ) time", in Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing (Philadelphia, PA, 1996), ACM, 1996, p. 47-55. | Article | Zbl 0924.68150

[7] G. Bennett, L. E. Dor, V. Goodman, W. B. Johnson & C. M. Newman - "On uncomplemented subspaces of L p , 1 < p < 2 ", Israel J. Math. 26 (1977), p. 178-187. | Article | Zbl 0339.46022

[8] K. Berman, H. Halpern, V. Kaftal & G. Weiss - "Matrix norm inequalities and the relative Dixmier property", Integral Equations Operator Theory 11 (1988), p. 28-48. | Article | Zbl 0647.47007

[9] R. Bhatia - Matrix analysis, Graduate Texts in Math., vol. 169, Springer, 1997. | Article | Zbl 0863.15001

[10] J. Bourgain, J. Lindenstrauss & V. Milman - "Approximation of zonoids by zonotopes", Acta Math. 162 (1989), p. 73-141. | Article | Zbl 0682.46008

[11] J. Bourgain & L. Tzafriri - "Invertibility of "large" submatrices with applications to the geometry of Banach spaces and harmonic analysis", Israel J. Math. 57 (1987), p. 137-224. | Article | Zbl 0631.46017

[12] J. Bourgain & L. Tzafriri,"Restricted invertibility of matrices and applications", in Analysis at Urbana, Vol. II (Urbana, IL, 1986-1987), London Math. Soc. Lecture Note Ser., vol. 138, Cambridge Univ. Press, 1989, p. 61-107. | Zbl 0698.47018

[13] J. Bourgain & L. Tzafriri, "On a problem of Kadison and Singer", J. reine angew. Math. 420 (1991), p. 1-43. | EuDML 153351 | Zbl 0729.47028

[14] B. Brinkman & M. Charikar - "On the impossibility of dimension reduction in l 1 ", J. ACM 52 (2005), p. 766-788. | Article | Zbl 1310.68199

[15] P. G. Casazza & J. C. Tremain - "Revisiting the Bourgain-Tzafriri restricted invertibility theorem", Oper. Matrices 3 (2009), p. 97-110. | Article | Zbl 1180.46009

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

[17] G. H. Golub & C. F. Van Loan- Matrix computations, third ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, 1996. | Zbl 0865.65009

[18] S. Hoory, N. Linial & A. Wigderson - "Expander graphs and their applications", Bull. Amer. Math. Soc. (N.S.) 43 (2006), p. 439-561. | Article | Zbl 1147.68608

[19] F. John - "Extremum problems with inequalities as subsidiary conditions", in Studies and Essays Presented to R. Courant on his 60th Birthday, January 8, 1948, Interscience Publishers, Inc., New York, N. Y., 1948, p. 187-204. | Zbl 0034.10503

[20] W. B. Johnson & J. Lindenstrauss - "Extensions of Lipschitz mappings into a Hilbert space", in Conference in modern analysis and probability (New Haven, Conn., 1982), Contemp. Math., vol. 26, Amer. Math. Soc., 1984, p. 189-206. | Article | Zbl 0539.46017

[21] W. B. Johnson & G. Schechtman - "Remarks on Talagrand's deviation inequality for Rademacher functions", in Functional analysis (Austin, TX, 1987/1989), Lecture Notes in Math., vol. 1470, Springer, 1991, p. 72-77. | Article | Zbl 0753.60024

[22] W. B. Johnson & G. Schechtman,"Finite dimensional subspaces of L p ", in Handbook of the geometry of Banach spaces, Vol. I, North-Holland, 2001, p. 837-870. | Article | Zbl 1012.46012

[23] A. Kolla, Y. Makarychev, A. Saberi & S.-H. Teng - "Subgraph sparsification and nearly optimal ultrasparsifiers", in STOC' 10 - Proceedings of the 2010 ACM International Symposium on Theory of Computing, ACM, 2010, p. 57-65. | Zbl 1293.05370

[24] A. Lubotzky, R. Phillips & P. Sarnak - "Ramanujan graphs", Combinatorica 8 (1988), p. 261-277. | Article | Zbl 0661.05035

[25] J. Matoušek - "On embedding expanders into l p spaces", Israel J. Math. 102 (1997), p. 189-197. | Article | Zbl 0947.46007

[26] M. Mendel& A. Naor - "Towards a calculus for non-linear spectral gaps", in Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010, p. 236-255, arXiv:0910.2041. | Article | Zbl 1288.05063

[27] A. Naor - " L 1 embeddings of the Heisenberg group and fast estimation of graph isoperimetry", in Proceedings of the International Congress of Mathematicians, Hyderabad India, 2010, http://www.cims.nyu.edu/˜naor/homepagefiles/ICM.pdf. | Zbl 1232.46021

[28] A. Naor & L. Silberman - "Poincaré inequalities, embeddings, and wild groups", Compos. Math. 147 (2011), p. 1546-1572. | Article | Zbl 1267.20057

[29] I. Newman & Y. Rabinovich - "Finite volume spaces and sparsification", preprint arXiv:1002.3541.

[30] A. Nilli - "On the second eigenvalue of a graph", Discrete Math. 91 (1991), p. 207-210. | Article | Zbl 0771.05064

[31] A. Pełczyński & N. Tomczak-Jaegermann - "On the length of faithful nuclear representations of finite rank operators", Mathematika 35 (1988), p. 126-143. | Article | Zbl 0654.47007

[32] M. Rudelson - "Approximate John's decompositions", in Geometric aspects of functional analysis (Israel, 1992-1994), Oper. Theory Adv. Appl., vol. 77, Birkhäuser, 1995, p. 245-249. | Zbl 0872.46014

[33] M. Rudelson, "Contact points of convex bodies", Israel J. Math. 101 (1997), p. 93-124. | Article | Zbl 0896.52008

[34] M. Rudelson, "Random vectors in the isotropic position", J. Funct. Anal. 164 (1999), p. 60-72. | Article | Zbl 0929.46021

[35] M. Rudelson & R. Vershynin - "Sampling from large matrices: an approach through geometric functional analysis", J. ACM 54 (2007), Art. 21. | Article | Zbl 1326.68333

[36] G. Schechtman - "Fine embeddings of finite-dimensional subspaces of L p , 1 p < 2 into l 1 m ", Proc. Amer. Math. Soc. 94 (1985), p. 617-623. | Zbl 0597.46019

[37] G. Schechtman, "More on embedding subspaces of L p in l r n ", Compositio Math. 61 (1987), p. 159-169. | EuDML 89819 | Numdam | Zbl 0659.46021

[38] G. Schechtman, "Tight embedding of subspaces of L p in p n for even p ", Proc. of the A.M.S. 139 (2011), p. 4419-4421. | Article | Zbl 1247.46013

[39] G. Schechtman & A. Zvavitch - "Embedding subspaces of L p into l p N , 0 < p < 1 ", Math. Nachr. 227 (2001), p. 133-142. | Article | Zbl 1046.46011

[40] I. J. Schoenberg - "On certain metric spaces arising from Euclidean spaces by a change of metric and their imbedding in Hilbert space", Ann. of Math. 38 (1937), p. 787-793. | Article | JFM 63.0363.03 | Zbl 0017.36101

[41] D. A. Spielman & N. Srivastava - "Graph sparsification by effective resistances", in STOC'08, ACM, 2008, p. 563-568. | Article | Zbl 1231.68184

[42] D. A. Spielman & N. Srivastava, "An elementary proof of the restricted invertibility theorem", Israel J. Math. (2012), doi://10.1007/s11856-011-0194-2. | Zbl 1261.46007

[43] D. A. Spielman & S.-H. Teng - "Nearly-linear time algorithms for graph partitioning, graph sparsiflcation, and solving linear systems", in Proceedings of the 36th Annual ACM Symposium on Theory of Computing, ACM, 2004, p. 81-90. | Zbl 1192.65048

[44] D. A. Spielman & S.-H. Teng, "Spectral sparsification of graphs", SIAM J. Comput. 40 (2011), p. 981-1025. | Article | Zbl 1228.68040

[45] D. A. Spielman & S.-H. Teng, "A local clustering algorithm for massive graphs and its application to nearly-linear time graph partitioning", preprint arXiv:0809.3232. | Article | Zbl 1286.68244

[46] D. A. Spielman & S.-H. Teng,"Nearly-linear time algorithms for graph partitioning, graph sparsiflcation, and solving linear systems", preprint arXiv:cs/0607105. | Zbl 1192.65048

[47] N. Srivastava - "On contact points of convex bodies", preprint http://www.cs.yale.edu/homes/srivastava/papers/contact.pdf, 2009. | Zbl 1264.52006

[48] N. Srivastava, "Spectral sparsification and restricted invertibility", Ph.D. Thesis, Yale University, 2010, http://www.cs.yale.edu/homes/srivastava/dissertation.pdf.

[49] M. Talagrand - "Embedding subspaces of L 1 into l 1 N ", Proc. Amer. Math. Soc. 108 (1990), p. 363-369. | Zbl 0723.46012

[50] M. Talagrand, "Embedding subspaces of L p in l p N ", in Geometric aspects of functional analysis (Israel, 1992-1994), Oper. Theory Adv. Appl., vol. 77, Birkhäuser, 1995, p. 311-325. | Zbl 0828.46011

[51] J. A. Tropp - "Column subset selection, matrix factorization, and eigenvalue optimization", in Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009, p. 978-986, arXiv:0806.4404. | Article

[52] J. A. Tropp, "User-friendly tail bounds for sums of random matrices", preprint arXiv:1004.4389. | Zbl 1259.60008

[53] R. Vershynin - "John's decompositions : selecting a large part", Israel J. Math. 122 (2001), p. 253-277. | Article | Zbl 0998.46006

[54] J. H. Wells & L. R. Williams - Embeddings and extensions in analysis, Ergebn. Math. Grenzg., vol. 84, Springer, 1975. | Zbl 0324.46034

[55] H. Weyl - "Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differentialgleichungen (mit einer Anwendung auf die Theorie der Hohlraumstrahlung)", Math. Ann. 71 (1912), p. 441-479. | Article | EuDML 158545 | JFM 43.0436.01

[56] A. Zvavitch - "More on embedding subspaces of L p into l p N , 0 < p < 1 ", in Geometric aspects of functional analysis, Lecture Notes in Math., vol. 1745, Springer, 2000, p. 269-280. | Article | Zbl 0972.46010