{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,14]],"date-time":"2025-11-14T21:34:27Z","timestamp":1763156067999,"version":"3.37.3"},"reference-count":99,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,12,16]],"date-time":"2019-12-16T00:00:00Z","timestamp":1576454400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,12,16]],"date-time":"2019-12-16T00:00:00Z","timestamp":1576454400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000008","name":"David and Lucile Packard Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000008","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2020,3]]},"DOI":"10.1007\/s00454-019-00162-2","type":"journal-article","created":{"date-parts":[[2019,12,16]],"date-time":"2019-12-16T18:04:40Z","timestamp":1576519480000},"page":"319-345","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Impossibility of Dimension Reduction in the Nuclear Norm"],"prefix":"10.1007","volume":"63","author":[{"given":"Assaf","family":"Naor","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gilles","family":"Pisier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gideon","family":"Schechtman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,12,16]]},"reference":[{"issue":"1\u20133","key":"162_CR1","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/S0012-365X(03)00227-9","volume":"273","author":"N Alon","year":"2003","unstructured":"Alon, N.: Problems and results in extremal combinatorics. I. Discrete Math. 273(1\u20133), 31\u201353 (2003)","journal-title":"Discrete Math."},{"key":"162_CR2","unstructured":"Andoni, A.: Nearest neighbor search in high-dimensional spaces. In: Murlak F., Sankowski P. (eds.) Proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science (MFCS 2011). Lecture Notes in Computer Science, vol. 6907, pp. 1. Springer, Berlin (2011). www.mit.edu\/~andoni\/papers\/nns-mfcs.pptx"},{"key":"162_CR3","doi-asserted-by":"crossref","unstructured":"Andoni, A., Charikar, M.S., Neiman, O., Nguy$$\\tilde{\\hat{{\\rm e}}}$$n, H.L.: Near linear lower bound for dimension reduction in $$\\ell _1$$. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS 2011), pp. 315\u2013323. IEEE Computer Society, Los Alamitos (2011)","DOI":"10.1109\/FOCS.2011.87"},{"key":"162_CR4","unstructured":"Andoni, A., Naor, A., Neiman, O.: On isomorphic dimension reduction in $$\\ell _1$$ (2017). Preprint"},{"key":"162_CR5","doi-asserted-by":"crossref","unstructured":"Andoni, A., Naor, A., Nikolov, A., Razenshteyn, I., Waingarten, E.: Data-dependent hashing via nonlinear spectral gaps. In: STOC\u201918\u2014Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 787\u2013800. ACM, New York (2018)","DOI":"10.1145\/3188745.3188846"},{"key":"162_CR6","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/BF02784520","volume":"132","author":"S Artstein","year":"2002","unstructured":"Artstein, S.: Proportional concentration phenomena on the sphere. Isr. J. Math. 132, 337\u2013358 (2002)","journal-title":"Isr. J. Math."},{"key":"162_CR7","unstructured":"Ball, K.: The Ribe programme. S\u00e9minaire Bourbaki. Vol. 2011\/2012. Expos\u00e9s 1043\u20131058. Ast\u00e9risque No. 352, Exp. No. 1047, 147\u2013159 (2013)"},{"issue":"2","key":"162_CR8","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/BF01896971","volume":"2","author":"K Ball","year":"1992","unstructured":"Ball, K.: Markov chains, Riesz transforms and Lipschitz maps. Geom. Funct. Anal. 2(2), 137\u2013172 (1992)","journal-title":"Geom. Funct. Anal."},{"issue":"3","key":"162_CR9","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/BF01231769","volume":"115","author":"K Ball","year":"1994","unstructured":"Ball, K., Carlen, E.A., Lieb, E.H.: Sharp uniform convexity and smoothness inequalities for trace norms. Invent. Math. 115(3), 463\u2013482 (1994)","journal-title":"Invent. Math."},{"issue":"2","key":"162_CR10","doi-asserted-by":"crossref","first-page":"643","DOI":"10.4007\/annals.2005.162.643","volume":"162","author":"Y Bartal","year":"2005","unstructured":"Bartal, Y., Linial, N., Mendel, M., Naor, A.: On metric Ramsey-type phenomena. Ann. Math. 162(2), 643\u2013709 (2005)","journal-title":"Ann. Math."},{"issue":"6","key":"162_CR11","doi-asserted-by":"crossref","first-page":"1092","DOI":"10.1007\/s000390050108","volume":"9","author":"S Bates","year":"1999","unstructured":"Bates, S., Johnson, W.B., Lindenstrauss, J., Preiss, D., Schechtman, G.: Affine approximation of Lipschitz functions and nonlinear quotients. Geom. Funct. Anal. 9(6), 1092\u20131127 (1999)","journal-title":"Geom. Funct. Anal."},{"key":"162_CR12","series-title":"American Mathematical Society Colloquium Publications","volume-title":"Geometric Nonlinear Functional Analysis, vol. 1","author":"Y Benyamini","year":"2000","unstructured":"Benyamini, Y., Lindenstrauss, J.: Geometric Nonlinear Functional Analysis, vol. 1. American Mathematical Society Colloquium Publications, vol. 48. American Mathematical Society, Providence (2000)"},{"key":"162_CR13","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0653-8","volume-title":"Matrix Analysis","author":"R Bhatia","year":"1997","unstructured":"Bhatia, R.: Matrix Analysis. Graduate Texts in Mathematics, vol. 169. Springer, New York (1997)"},{"issue":"1\u20132","key":"162_CR14","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1007\/BF02776078","volume":"52","author":"J Bourgain","year":"1985","unstructured":"Bourgain, J.: On Lipschitz embedding of finite metric spaces in Hilbert space. Isr. J. Math. 52(1\u20132), 46\u201352 (1985)","journal-title":"Isr. J. Math."},{"issue":"1\u20132","key":"162_CR15","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BF02392835","volume":"162","author":"J Bourgain","year":"1989","unstructured":"Bourgain, J., Lindenstrauss, J., Milman, V.: Approximation of zonoids by zonotopes. Acta Math. 162(1\u20132), 73\u2013141 (1989)","journal-title":"Acta Math."},{"issue":"1","key":"162_CR16","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1090\/S0002-9947-1986-0819949-8","volume":"294","author":"J Bourgain","year":"1986","unstructured":"Bourgain, J., Milman, V., Wolfson, H.: On type of metric spaces. Trans. Amer. Math. Soc. 294(1), 295\u2013317 (1986)","journal-title":"Trans. Amer. Math. Soc."},{"volume-title":"Handbook of Robust Low-Rank and Sparse Matrix Decomposition: Applications in Image and Video Processing","year":"2016","key":"162_CR17","unstructured":"Bouwmans, T., Serhat-Aybat, N., Zahzah, E. (eds.): Handbook of Robust Low-Rank and Sparse Matrix Decomposition: Applications in Image and Video Processing. CRC Press, Boca Raton (2016)"},{"issue":"5","key":"162_CR18","doi-asserted-by":"crossref","first-page":"766","DOI":"10.1145\/1089023.1089026","volume":"52","author":"B Brinkman","year":"2005","unstructured":"Brinkman, B., Charikar, M.: On the impossibility of dimension reduction in $$l_1$$. J. ACM 52(5), 766\u2013788 (2005)","journal-title":"J. ACM"},{"issue":"6","key":"162_CR19","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1007\/s10208-009-9045-5","volume":"9","author":"EJ Cand\u00e8s","year":"2009","unstructured":"Cand\u00e8s, E.J., Recht, B.: Exact matrix completion via convex optimization. Found. Comput. Math. 9(6), 717\u2013772 (2009)","journal-title":"Found. Comput. Math."},{"issue":"5","key":"162_CR20","doi-asserted-by":"crossref","first-page":"2053","DOI":"10.1109\/TIT.2010.2044061","volume":"56","author":"EJ Cand\u00e8s","year":"2010","unstructured":"Cand\u00e8s, E.J., Tao, T.: The power of convex relaxation: near-optimal matrix completion. IEEE Trans. Inf. Theory 56(5), 2053\u20132080 (2010)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"162_CR21","series-title":"Contemporary Mathematics","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1090\/conm\/529\/10428","volume-title":"Trace Inequalities and Quantum Entropy: An Introductory Course. Entropy and the Quantum","author":"E Carlen","year":"2010","unstructured":"Carlen, E.: Trace Inequalities and Quantum Entropy: An Introductory Course. Entropy and the Quantum. Contemporary Mathematics, vol. 529, pp. 73\u2013140. American Mathematical Society, Providence (2010)"},{"key":"162_CR22","unstructured":"Charikar, M., Sahai, A.: Dimension reduction in the $$\\ell _1$$ norm. In: Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), pp. 551\u2013560. IEEE Computer Society (2002)"},{"issue":"3","key":"162_CR23","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1090\/S0002-9947-1936-1501880-4","volume":"40","author":"JA Clarkson","year":"1936","unstructured":"Clarkson, J.A.: Uniformly convex spaces. Trans. Amer. Math. Soc. 40(3), 396\u2013414 (1936)","journal-title":"Trans. Amer. Math. Soc."},{"key":"162_CR24","doi-asserted-by":"crossref","unstructured":"Deshpande, A., Tulsiani, M., Vishnoi, N.K.: Algorithms and hardness for subspace approximation. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 482\u2013496. SIAM, Philadelphia (2011)","DOI":"10.1137\/1.9781611973082.39"},{"issue":"3","key":"162_CR25","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1112\/jlms\/s2-30.3.481","volume":"30","author":"SJ Dilworth","year":"1984","unstructured":"Dilworth, S.J.: On the dimension of almost Hilbertian subspaces of quotient spaces. J. London Math. Soc. 30(3), 481\u2013485 (1984)","journal-title":"J. London Math. Soc."},{"key":"162_CR26","doi-asserted-by":"crossref","first-page":"9","DOI":"10.24033\/bsmf.1436","volume":"81","author":"J Dixmier","year":"1953","unstructured":"Dixmier, J.: Formes lin\u00e9aires sur un anneau d\u2019op\u00e9rateurs. Bull. Soc. Math. France 81, 9\u201339 (1953)","journal-title":"Bull. Soc. Math. France"},{"key":"162_CR27","unstructured":"Dixmier, J.: Les alg\u00e8bres d\u2019op\u00e9rateurs dans l\u2019espace hilbertien (alg\u00e8bres de von Neumann). Les Grands Classiques Gauthier-Villars. \u00c9ditions Jacques Gabay, Paris. Reprint of the second 1969 edition (1996)"},{"key":"162_CR28","unstructured":"Dvoretzky, A.: Some results on convex bodies and Banach spaces. In: Proceedings of the International Symposium on Linear Spaces, pp. 123\u2013160. Jerusalem Academic Press, Jerusalem (1961)"},{"key":"162_CR29","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1007\/BF02589549","volume":"8","author":"P Enflo","year":"1969","unstructured":"Enflo, P.: On the nonexistence of uniform homeomorphisms between $$L_{p}$$-spaces. Ark. Mat. 8, 103\u2013105 (1969)","journal-title":"Ark. Mat."},{"key":"162_CR30","unstructured":"Enflo, P.: On infinite-dimensional topological groups. In: S\u00e9minaire sur la G\u00e9om\u00e9trie des Espaces de Banach (1977\u20131978), Exp. No. 10\u201311. \u00c9cole Polytechnique, Palaiseau (1978)"},{"key":"162_CR31","unstructured":"Eskenazis, A., Mendel, M., Naor, A.: Diamond convexity: a bifurcation in the Ribe program (2017). Preprint"},{"issue":"1\u20132","key":"162_CR32","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/BF02392234","volume":"139","author":"T Figiel","year":"1977","unstructured":"Figiel, T., Lindenstrauss, J., Milman, V.D.: The dimension of almost spherical sections of convex bodies. Acta Math. 139(1\u20132), 53\u201394 (1977)","journal-title":"Acta Math."},{"key":"162_CR33","series-title":"Progress in Mathematics","volume-title":"Metric Structures for Riemannian and Non-Riemannian Spaces","author":"M Gromov","year":"1999","unstructured":"Gromov, M.: Metric Structures for Riemannian and Non-Riemannian Spaces. Progress in Mathematics, vol. 152. Birkh\u00e4user, Boston (1999)"},{"issue":"2","key":"162_CR34","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/s11263-016-0930-5","volume":"121","author":"S Gu","year":"2017","unstructured":"Gu, S., Xie, Q., Meng, D., Zuo, W., Feng, X., Zhang, L.: Weighted nuclear norm minimization and its applications to low level vision. Int. J. Comput. Vis. 121(2), 183\u2013208 (2017)","journal-title":"Int. J. Comput. Vis."},{"key":"162_CR35","doi-asserted-by":"crossref","unstructured":"Gu, S., Zhang, L., Zuo, W., Feng, X.: Weighted nuclear norm minimization with application to image denoising. In: 2014 IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2014), pp. 2862\u20132869. IEEE Computer Society (2014)","DOI":"10.1109\/CVPR.2014.366"},{"issue":"2","key":"162_CR36","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1007\/s00493-004-0015-x","volume":"24","author":"A Gupta","year":"2004","unstructured":"Gupta, A., Newman, I., Rabinovich, Yu., Sinclair, A.: Cuts, trees and $$l_1$$-embeddings of graphs. Combinatorica 24(2), 233\u2013269 (2004)","journal-title":"Combinatorica"},{"key":"162_CR37","unstructured":"Gutman, I.: The energy of a graph. In: 10. Steierm\u00e4rkisches Mathematisches Symposium (Stift Rein, Graz, 1978). Ber. Math.-Statist. Sekt. Forsch. Graz (100\u2013105), Ber. No. 103 (1978)"},{"key":"162_CR38","doi-asserted-by":"crossref","unstructured":"Harchaoui, Z., Douze, M., Paulin, M., Dud\u00edk, M., Malick, J.: Large-scale image classification with trace-norm regularization. In: Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition, pp. 3386\u20133393. IEEE Computer Society (2012)","DOI":"10.1109\/CVPR.2012.6248078"},{"key":"162_CR39","first-page":"2348","volume-title":"Advances in Neural Information Processing Systems","author":"M Hardt","year":"2012","unstructured":"Hardt, M., Ligett, K., McSherry, F.: A simple and practical algorithm for differentially private data release. In: Bartlett, P.L., et al. (eds.) Advances in Neural Information Processing Systems, vol. 2, pp. 2348\u20132356. Curran Associates, New York (2012)"},{"key":"162_CR40","series-title":"Part I. Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1007\/978-3-642-22006-7_8","volume-title":"Automata, Languages and Programming (ICALP 2011)","author":"AW Harrow","year":"2011","unstructured":"Harrow, A.W., Montanaro, A., Short, A.J.: Limitations on quantum dimensionality reduction. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) Automata, Languages and Programming (ICALP 2011). Part I. Lecture Notes in Computer Science, vol. 6755, pp. 86\u201397. Springer, Heidelberg (2011)"},{"key":"162_CR41","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0131-8","volume-title":"Lectures on Analysis on Metric Spaces. Universitext.","author":"J Heinonen","year":"2001","unstructured":"Heinonen, J.: Lectures on Analysis on Metric Spaces. Universitext. Springer, New York (2001)"},{"issue":"11","key":"162_CR42","doi-asserted-by":"crossref","first-page":"3415","DOI":"10.4171\/JEMS\/906","volume":"21","author":"T Hyt\u00f6nen","year":"2019","unstructured":"Hyt\u00f6nen, T., Naor, A.: Heat flow and quantitative differentiation. J. Eur. Math. Soc. (JEMS) 21(11), 3415\u20133466 (2019)","journal-title":"J. Eur. Math. Soc. (JEMS)"},{"issue":"3","key":"162_CR43","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/1273340.1273347","volume":"3","author":"P Indyk","year":"2007","unstructured":"Indyk, P., Naor, A.: Nearest-neighbor-preserving embeddings. ACM Trans. Algorithms 3(3), 31 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"162_CR44","series-title":"London Mathematical Society Lecture Note Series","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511721519","volume-title":"Introduction to Uniform Spaces","author":"IM James","year":"1990","unstructured":"James, I.M.: Introduction to Uniform Spaces. London Mathematical Society Lecture Note Series, vol. 144. Cambridge University Press, Cambridge (1990)"},{"key":"162_CR45","series-title":"Contemporary Mathematics","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1090\/conm\/026\/737400","volume-title":"Conference in Modern Analysis and Probability","author":"WB Johnson","year":"1984","unstructured":"Johnson, W.B., Lindenstrauss, J.: Extensions of Lipschitz mappings into a Hilbert space. In: Beals, A., et al. (eds.) Conference in Modern Analysis and Probability. Contemporary Mathematics, vol. 26, pp. 189\u2013206. American Mathematical Society, Providence (1984)"},{"key":"162_CR46","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/BFb0078145","volume-title":"Geometrical Aspects of Functional Analysis (1985\/86)","author":"WB Johnson","year":"1987","unstructured":"Johnson, W.B., Lindenstrauss, J., Schechtman, G.: On Lipschitz embedding of finite metric spaces in low-dimensional normed spaces. In: Lindenstrauss, J., Milman, V.D. (eds.) Geometrical Aspects of Functional Analysis (1985\/86). Lecture Notes in Mathematics, vol. 1267, pp. 177\u2013184. Springer, Berlin (1987)"},{"issue":"3","key":"162_CR47","doi-asserted-by":"crossref","first-page":"542","DOI":"10.1007\/s00454-009-9193-z","volume":"43","author":"WB Johnson","year":"2010","unstructured":"Johnson, W.B., Naor, A.: The Johnson\u2013Lindenstrauss lemma almost characterizes Hilbert space, but not quite. Discrete Comput. Geom. 43(3), 542\u2013553 (2010)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"162_CR48","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1142\/S1793525309000114","volume":"1","author":"WB Johnson","year":"2009","unstructured":"Johnson, W.B., Schechtman, G.: Diamond graphs and super-reflexivity. J. Topol. Anal. 1(2), 177\u2013189 (2009)","journal-title":"J. Topol. Anal."},{"issue":"1","key":"162_CR49","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/s000390050003","volume":"10","author":"TJ Laakso","year":"2000","unstructured":"Laakso, T.J.: Ahlfors $$Q$$-regular spaces with arbitrary $$Q>1$$ admitting weak Poincar\u00e9 inequality. Geom. Funct. Anal. 10(1), 111\u2013123 (2000)","journal-title":"Geom. Funct. Anal."},{"issue":"1","key":"162_CR50","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1007\/s11856-014-1088-x","volume":"203","author":"V Lafforgue","year":"2014","unstructured":"Lafforgue, V., Naor, A.: Vertical versus horizontal Poincar\u00e9 inequalities on the Heisenberg group. Isr. J. Math. 203(1), 309\u2013339 (2014)","journal-title":"Isr. J. Math."},{"issue":"1\u20133","key":"162_CR51","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1023\/A:1012093209450","volume":"87","author":"U Lang","year":"2001","unstructured":"Lang, U., Plaut, C.: Bilipschitz embeddings of metric spaces into space forms. Geom. Dedicata 87(1\u20133), 285\u2013307 (2001)","journal-title":"Geom. Dedicata"},{"key":"162_CR52","unstructured":"Larsen, K.G., Nelson, J.: Optimality of the Johnson\u2013Lindenstrauss lemma. In: Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017), pp. 633\u2013638. IEEE Computer Society, Los Alamitos (2017). https:\/\/arxiv.org\/abs\/1609.02094"},{"issue":"4","key":"162_CR53","first-page":"745","volume":"14","author":"JR Lee","year":"2004","unstructured":"Lee, J.R., Naor, A.: Embedding the diamond graph in $$L_p$$ and dimension reduction in $$L_1$$. Geom. Funct. Anal. 14(4), 745\u2013747 (2004)","journal-title":"Geom. Funct. Anal."},{"issue":"5","key":"162_CR54","doi-asserted-by":"crossref","first-page":"1609","DOI":"10.1007\/s00039-008-0689-0","volume":"18","author":"JR Lee","year":"2009","unstructured":"Lee, J.R., Naor, A., Peres, Y.: Trees and Markov convexity. Geom. Funct. Anal. 18(5), 1609\u20131659 (2009)","journal-title":"Geom. Funct. Anal."},{"issue":"8","key":"162_CR55","doi-asserted-by":"crossref","first-page":"1180","DOI":"10.1016\/j.ejc.2004.07.002","volume":"26","author":"JR Lee","year":"2005","unstructured":"Lee, J.R., Mendel, M., Naor, A.: Metric structures in $$L_1$$: dimension, snowflakes, and average distortion. Eur. J. Comb. 26(8), 1180\u20131190 (2005)","journal-title":"Eur. J. Comb."},{"issue":"2","key":"162_CR56","doi-asserted-by":"crossref","first-page":"207","DOI":"10.4064\/sm-63-2-207-212","volume":"63","author":"DR Lewis","year":"1978","unstructured":"Lewis, D.R.: Finite dimensional subspaces of $$L_{p}$$. Stud. Math. 63(2), 207\u2013212 (1978)","journal-title":"Stud. Math."},{"key":"162_CR57","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1145\/2448496.2448529","volume-title":"Proceedings 16th International Conference on Database Theory (ICDT\u201913)","author":"C Li","year":"2013","unstructured":"Li, C., Miklau, G.: Optimal error of query sets under the differentially-private matrix mechanism. In: Tan, W., et al. (eds.) Proceedings 16th International Conference on Database Theory (ICDT\u201913), pp. 272\u2013283. ACM, New York (2013)"},{"key":"162_CR58","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4614-4220-2","volume-title":"Graph Energy","author":"X Li","year":"2012","unstructured":"Li, X., Shi, Y., Gutman, I.: Graph Energy. Springer, New York (2012)"},{"key":"162_CR59","unstructured":"Li, Y., Woodruff, D.P.: Embeddings of Schatten norms with applications to data streams (2017). To appear in Proceedings of 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017. https:\/\/arxiv.org\/abs\/1702.05626"},{"key":"162_CR60","unstructured":"Li, Y., Woodruff, D.P.: Embeddings of Schatten norms with applications to data streams. In: Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). LIPIcs. Leibniz International Proceedings in Informatics, vol.\u00a080, Art. No. 60. Schloss Dagstuhl. Leibniz-Zentrum f\u00fcr Informatik, Wadern (2017)"},{"issue":"2","key":"162_CR61","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF01200757","volume":"15","author":"N Linial","year":"1995","unstructured":"Linial, N., London, E., Rabinovich, Yu.: The geometry of graphs and some of its algorithmic applications. Combinatorica 15(2), 215\u2013245 (1995)","journal-title":"Combinatorica"},{"issue":"1","key":"162_CR62","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/BF01170633","volume":"38","author":"K L\u00f6wner","year":"1934","unstructured":"L\u00f6wner, K.: \u00dcber monotone Matrixfunktionen. Math. Z. 38(1), 177\u2013216 (1934)","journal-title":"Math. Z."},{"issue":"2","key":"162_CR63","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1016\/j.aim.2005.04.010","volume":"203","author":"T Mart\u00ednez","year":"2006","unstructured":"Mart\u00ednez, T., Torrea, J.L., Xu, Q.: Vector-valued Littlewood\u2013Paley\u2013Stein theory for semigroups. Adv. Math. 203(2), 430\u2013475 (2006)","journal-title":"Adv. Math."},{"issue":"1","key":"162_CR64","first-page":"51","volume":"33","author":"J Matou\u0161ek","year":"1992","unstructured":"Matou\u0161ek, J.: Note on bi-Lipschitz embeddings into normed spaces. Comment. Math. Univ. Carolin. 33(1), 51\u201355 (1992)","journal-title":"Comment. Math. Univ. Carolin."},{"key":"162_CR65","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/BF02761110","volume":"93","author":"J Matou\u0161ek","year":"1996","unstructured":"Matou\u0161ek, J.: On the distortion required for embedding finite metric spaces into normed spaces. Isr. J. Math. 93, 333\u2013344 (1996)","journal-title":"Isr. J. Math."},{"key":"162_CR66","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/BF02771613","volume":"5","author":"CA McCarthy","year":"1967","unstructured":"McCarthy, C.A.: $$c_{p}$$. Isr. J. Math. 5, 249\u2013271 (1967)","journal-title":"Isr. J. Math."},{"issue":"2","key":"162_CR67","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1016\/j.aim.2003.12.001","volume":"189","author":"M Mendel","year":"2004","unstructured":"Mendel, M., Naor, A.: Euclidean quotients of finite metric spaces. Adv. Math. 189(2), 451\u2013494 (2004)","journal-title":"Adv. Math."},{"issue":"1","key":"162_CR68","doi-asserted-by":"crossref","first-page":"287","DOI":"10.4171\/JEMS\/362","volume":"15","author":"M Mendel","year":"2013","unstructured":"Mendel, M., Naor, A.: Markov convexity and local rigidity of distorted metrics. J. Eur. Math. Soc. (JEMS) 15(1), 287\u2013337 (2013)","journal-title":"J. Eur. Math. Soc. (JEMS)"},{"key":"162_CR69","doi-asserted-by":"crossref","first-page":"163","DOI":"10.2478\/agms-2013-0003","volume":"1","author":"M Mendel","year":"2013","unstructured":"Mendel, M., Naor, A.: Spectral calculus and Lipschitz extension for barycentric metric spaces. Anal. Geom. Metr. Spaces 1, 163\u2013199 (2013)","journal-title":"Anal. Geom. Metr. Spaces"},{"key":"162_CR70","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10240-013-0053-2","volume":"119","author":"M Mendel","year":"2014","unstructured":"Mendel, M., Naor, A.: Nonlinear spectral calculus and super-expanders. Publ. Math. Inst. Hautes \u00c9tud. Sci. 119, 1\u201395 (2014)","journal-title":"Publ. Math. Inst. Hautes \u00c9tud. Sci."},{"issue":"4","key":"162_CR71","first-page":"28","volume":"5","author":"VD Milman","year":"1971","unstructured":"Milman, V.D.: A new proof of A. Dvoretzky\u2019s theorem on cross-sections of convex bodies. Funkcional Anal. Prilo\u017een. 5(4), 28\u201337 (1971)","journal-title":"Funkcional Anal. Prilo\u017een."},{"issue":"3","key":"162_CR72","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1090\/S0002-9939-1985-0787891-1","volume":"94","author":"VD Milman","year":"1985","unstructured":"Milman, V.D.: Almost Euclidean quotient spaces of subspaces of a finite-dimensional normed space. Proc. Am. Math. Soc. 94(3), 445\u2013449 (1985)","journal-title":"Proc. Am. Math. Soc."},{"issue":"4","key":"162_CR73","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/BF01647331","volume":"79","author":"L Mirsky","year":"1975","unstructured":"Mirsky, L.: A trace inequality of John von Neumann. Monatsh. Math. 79(4), 303\u2013306 (1975)","journal-title":"Monatsh. Math."},{"issue":"2","key":"162_CR74","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/s11537-012-1222-7","volume":"7","author":"A Naor","year":"2012","unstructured":"Naor, A.: An introduction to the Ribe program. Jpn. J. Math. 7(2), 167\u2013233 (2012)","journal-title":"Jpn. J. Math."},{"issue":"3","key":"162_CR75","doi-asserted-by":"crossref","first-page":"991","DOI":"10.4007\/annals.2016.184.3.9","volume":"184","author":"A Naor","year":"2016","unstructured":"Naor, A.: Discrete Riesz transforms and sharp metric $$X_p$$ inequalities. Ann. Math. 184(3), 991\u20131016 (2016)","journal-title":"Ann. Math."},{"key":"162_CR76","unstructured":"Naor, A.: A spectral gap precludes low-dimensional embeddings. In: Aronov, B., Katz, M.J. (eds.) 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics, vol.\u00a077, pp. 50:1\u201350:16. Schloss Dagstuhl. Leibniz-Zentrum f\u00fcr Informatik, Wadern (2017)"},{"key":"162_CR77","doi-asserted-by":"crossref","unstructured":"Naor, A.: Metric dimension reduction: a snapshot of the Ribe program. In: Proceedings of the 2018 International Congress of Mathematicians, Rio de Janeiro, vol. I, pp. 767\u2013846 (2018)","DOI":"10.1142\/9789813272880_0029"},{"key":"162_CR78","doi-asserted-by":"crossref","first-page":"e3","DOI":"10.1017\/fmp.2016.1","volume":"4","author":"A Naor","year":"2016","unstructured":"Naor, A., Schechtman, G.: Metric $$X_p$$ inequalities. Forum Math. Pi 4, e3 (2016)","journal-title":"Forum Math. Pi"},{"key":"162_CR79","unstructured":"Naor, A., Schechtman, G.: Obstructions to metric embeddings of Schatten classes (2017). Preprint"},{"issue":"1","key":"162_CR80","doi-asserted-by":"crossref","first-page":"171","DOI":"10.4007\/annals.2018.188.1.4","volume":"188","author":"A Naor","year":"2018","unstructured":"Naor, A., Young, R.: Vertical perimeter versus horizontal perimeter. Ann. Math. 188(1), 171\u2013279 (2018)","journal-title":"Ann. Math."},{"key":"162_CR81","unstructured":"Naor, A., Young, R.: Foliated corona decompositions (2019). Preprint"},{"issue":"2","key":"162_CR82","doi-asserted-by":"crossref","first-page":"1472","DOI":"10.1016\/j.jmaa.2006.03.072","volume":"326","author":"V Nikiforov","year":"2007","unstructured":"Nikiforov, V.: The energy of graphs and matrices. J. Math. Anal. Appl. 326(2), 1472\u20131475 (2007)","journal-title":"J. Math. Anal. Appl."},{"issue":"1\u20132","key":"162_CR83","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1112\/S0025579300001005","volume":"55","author":"S-I Ohta","year":"2009","unstructured":"Ohta, S.-I.: Markov type of Alexandrov spaces of non-negative curvature. Mathematika 55(1\u20132), 177\u2013189 (2009)","journal-title":"Mathematika"},{"issue":"3\u20134","key":"162_CR84","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1007\/BF02760337","volume":"20","author":"G Pisier","year":"1975","unstructured":"Pisier, G.: Martingales with values in uniformly convex spaces. Isr. J. Math. 20(3\u20134), 326\u2013350 (1975)","journal-title":"Isr. J. Math."},{"issue":"1","key":"162_CR85","first-page":"3","volume":"37","author":"G Pisier","year":"1978","unstructured":"Pisier, G.: Some results on Banach spaces without local unconditional structure. Compos. Math. 37(1), 3\u201319 (1978)","journal-title":"Compos. Math."},{"key":"162_CR86","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/BFb0076302","volume-title":"Probability and Analysis","author":"G Pisier","year":"1986","unstructured":"Pisier, G.: Probabilistic methods in the geometry of Banach spaces. In: Letta, G., Pratelli, M. (eds.) Probability and Analysis. Lecture Notes in Mathematics, vol. 1206, pp. 167\u2013241. Springer, Berlin (1986)"},{"key":"162_CR87","first-page":"3413","volume":"12","author":"B Recht","year":"2011","unstructured":"Recht, B.: A simpler approach to matrix completion. J. Mach. Learn. Res. 12, 3413\u20133430 (2011)","journal-title":"J. Mach. Learn. Res."},{"issue":"3","key":"162_CR88","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1137\/070697835","volume":"52","author":"B Recht","year":"2010","unstructured":"Recht, B., Fazel, M., Parrilo, P.A.: Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev. 52(3), 471\u2013501 (2010)","journal-title":"SIAM Rev."},{"issue":"2","key":"162_CR89","doi-asserted-by":"crossref","first-page":"825","DOI":"10.1007\/s11856-012-0137-6","volume":"195","author":"O Regev","year":"2013","unstructured":"Regev, O.: Entropy-based bounds on dimension reduction in $$L_1$$. Isr J. Math. 195(2), 825\u2013832 (2013)","journal-title":"Isr J. Math."},{"key":"162_CR90","unstructured":"Regev, O., Vidick, T.: Bounds on dimension reduction in the nuclear norm (2019). https:\/\/arxiv.org\/abs\/1901.09480"},{"issue":"2","key":"162_CR91","first-page":"159","volume":"61","author":"G Schechtman","year":"1987","unstructured":"Schechtman, G.: More on embedding subspaces of $$L_p$$ in $$l^n_r$$. Compos. Math. 61(2), 159\u2013169 (1987)","journal-title":"Compos. Math."},{"key":"162_CR92","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1002\/1522-2616(200107)227:1<133::AID-MANA133>3.0.CO;2-8","volume":"227","author":"G Schechtman","year":"2001","unstructured":"Schechtman, G., Zvavitch, A.: Embedding subspaces of $$L_p$$ into $$l^N_p$$, $$0