Sparse quadratic forms and their geometric applications [following Baston, Spielman and Srivastava]

Naor, Assaf

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.

Zbl

@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.},
     series = {Ast\'erisque},
     note = {talk:1033},
     pages = {189--217},
     publisher = {Soci\'et\'e math\'ematique de France},
     number = {348},
     year = {2012},
     zbl = {1264.15024},
     language = {en},
     url = {http://www.numdam.org/item/AST_2012__348__189_0/}
}

TY  - CHAP
AU  - Naor, Assaf
TI  - Sparse quadratic forms and their geometric applications [following Baston, Spielman and Srivastava]
BT  - Séminaire Bourbaki Volume 2010/2011 Exposés 1027-1042. Avec table par noms d'auteurs de 1948/49 à 2009/10.
AU  - Collectif
T3  - Astérisque
N1  - talk:1033
PY  - 2012
SP  - 189
EP  - 217
IS  - 348
PB  - Société mathématique de France
UR  - http://www.numdam.org/item/AST_2012__348__189_0/
LA  - en
ID  - AST_2012__348__189_0
ER  -

%0 Book Section
%A Naor, Assaf
%T Sparse quadratic forms and their geometric applications [following Baston, Spielman and Srivastava]
%B Séminaire Bourbaki Volume 2010/2011 Exposés 1027-1042. Avec table par noms d'auteurs de 1948/49 à 2009/10.
%A Collectif
%S Astérisque
%Z talk:1033
%D 2012
%P 189-217
%N 348
%I Société mathématique de France
%U http://www.numdam.org/item/AST_2012__348__189_0/
%G en
%F 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://www.numdam.org/item/AST_2012__348__189_0/

Bibliographie
Cité par

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

[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. | DOI | Zbl

[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

[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

[6] A. A. Benczúr & D. R. Karger - "Approximating s-t minimum cuts in $\tilde{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. | DOI | Zbl

[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. | DOI | Zbl

[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. | DOI | Zbl

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

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

[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. | DOI | Zbl

[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

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

[14] B. Brinkman & M. Charikar - "On the impossibility of dimension reduction in $l_{1}$ ", J. ACM 52 (2005), p. 766-788. | DOI | Zbl

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

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

[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

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

[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

[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. | DOI | Zbl

[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. | DOI | Zbl

[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. | DOI | Zbl

[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

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

[25] J. Matoušek - "On embedding expanders into $l_{p}$ spaces", Israel J. Math. 102 (1997), p. 189-197. | DOI | Zbl

[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. | DOI | Zbl

[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

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

[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. | DOI | Zbl

[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. | DOI | Zbl

[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

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

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

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

[36] G. Schechtman - "Fine embeddings of finite-dimensional subspaces of $L_{p}, 1 \leq p < 2$ into $l_{1}^{m}$ ", Proc. Amer. Math. Soc. 94 (1985), p. 617-623. | Zbl

[37] G. Schechtman, "More on embedding subspaces of $L_{p}$ in $l_{r}^{n}$ ", Compositio Math. 61 (1987), p. 159-169. | EuDML | Numdam | Zbl

[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. | DOI | Zbl

[39] G. Schechtman & A. Zvavitch - "Embedding subspaces of $L_{p}$ into $l_{p}^{N}, 0 < p < 1$ ", Math. Nachr. 227 (2001), p. 133-142. | DOI | Zbl

[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. | DOI | JFM | Zbl

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

[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

[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

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

[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. | DOI | Zbl

[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

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

[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

[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

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

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

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

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

[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. | DOI | EuDML | JFM

[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. | DOI | Zbl