Vertical perimeter versus horizontal perimeter. (English) Zbl 1397.46020

Naor, Assaf; Young, Robert

Ann. Math. (2) 188, No. 1, 171-279 (2018).

The topic of this paper arose as a way to approach one of the fundamental problems in Computer Science: find the most efficient (polynomial) approximation algorithm for the sparsest cut problem. (The problem itself is known to be NP-hard, see [F. Shahrokhi and D. W. Matula, J. Assoc. Comput. Mach. 37, No. 2, 318–334 (1990; Zbl 0696.68071)]). The Goemans-Linial semidefinite approximation algorithm, see [M. X. Goemans, Math. Program. 79, No. 1–3 (B), 143–161 (1997; Zbl 0887.90139)], which is asymptotically the best known at the moment, has approximation ratio \(\rho_{\mathrm{GL}}(n)\) (for problems of size \(n\)) equal to the supremum of the \(L_1\)-distortion over all \(n\)-point metric spaces of negative type.
The estimate of this distortion from below is the main goal of the present paper. One of the main results of the paper (Theorem 5): For every integer \(n\geq 2\), there is an absolute constant \(c>0\) such that \(c\sqrt{\log n}\leq\rho_{\mathrm{GL}}(n)\leq (\log n)^{\frac12+o(1)}\). Only the leftmost inequality is proved in the paper, the rightmost inequality was proved in [S. Arora et al., J. Am. Math. Soc. 21, No. 1, 1–21 (2008; Zbl 1132.68070)].
The proof of the leftmost inequality uses the approach suggested by J. R. Lee and A. Naor [“\(L_p\) metrics on the Heisenberg group and the Goemans-Linial conjecture”, in: Proceedings of 47th annual IEEE Symposium on Foundations of Computer Science. Los Alamitos, CA: IEEE Computer Society. 99–108 (2006; doi:10.1109/focs.2006.47)], namely, the observation that Heisenberg groups admit equivalent metrics of negative type and therefore lower estimates for \(\rho_{\mathrm{GL}}(n)\) can be obtained by studying the \(L_1\)-distortions of finite subsets of Heisenberg groups. It should be mentioned that J. Cheeger et al. [Acta Math. 207, No. 2, 291–373 (2011; Zbl 1247.46020)] proved that \(\rho_{\mathrm{GL}}(n)\geq c (\log n)^\delta\) for some absolute constants \(\delta, c>0\). The goal of the present paper is to get the maximal possible exponent \(\delta=\frac12\). In fact, the upper and lower bounds in Theorem 5 coincide up to lower-order factors. Theorem 5 in the paper is derived from the result stated below (Theorem 3) on Heisenberg groups which the authors call “vertical versus horizontal isoperimetric inequality”.
It is important to mention that the Heisenberg groups studied in this paper can be regarded as high-dimensional generalizations of what is called the Heisenberg group in many sources. We reproduce the description from the authors’ abstract: “Given \(k\in \mathbb{N}\), the \(k\)-th discrete Heisenberg group, denoted by \(\mathbb{H}_{\mathbb{Z}}^{2k+1}\), is the group generated by the elements \(a_1,b_1,\dots,a_k,b_k,c\), subject to the commutator relations \([a_1,b_1]=\ldots=[a_k,b_k]=c\), while all the other pairs of elements from this generating set are required to commute, i.e., for every distinct \(i,j\in \{1,\dots,k\}\), we have \([a_i,a_j]=[b_i,b_j]=[a_i,b_j]=[a_i,c]=[b_i,c]=1\) (in particular, this implies that \(c\) is in the center of \(\mathbb{H}_{\mathbb{Z}}^{2k+1}\)). Denote \(\mathfrak{S}_k=\{a_1,b_1,a_1^{-1},b_1^{-1},\ldots,a_k,b_k,a_k^{-1},b_k^{-1}\}\). The horizontal boundary of \(\Omega\subset \mathbb{H}_{\mathbb{Z}}^{2k+1}\), denoted by \(\partial_{\mathrm h}\Omega\), is the set of all those pairs \((x,y)\in \Omega\times (\mathbb{H}_{\mathbb{Z}}^{2k+1}\setminus \Omega)\) such that \(x^{-1}y\in \mathfrak{S}_k\). The horizontal perimeter of \(\Omega\) is the cardinality \(|\partial_{\mathrm h}\Omega|\) of \(\partial_{\mathrm h}\Omega\), i.e., it is the total number of edges incident to \(\Omega\) in the Cayley graph induced by \(\mathfrak{S}_k\). For \(t\in \mathbb{N}\), define \(\partial^t_{\mathrm v} \Omega\) to be the set of all those pairs \((x,y)\in \Omega\times (\mathbb{H}_{\mathbb{Z}}^{2k+1}\setminus \Omega)\) such that \(x^{-1}y\in \{c^t,c^{-t}\}\). Thus, \(|\partial^t_{\mathrm v}\Omega|\) is the total number of edges incident to \(\Omega\) in the (disconnected) Cayley graph induced by \(\{c^t,c^{-t}\}\subset \mathbb{H}_{\mathbb{Z}}^{2k+1}\). The vertical perimeter of \(\Omega\) is defined by \(|\partial_{\mathrm v}\Omega|= \sqrt{\sum_{t=1}^\infty |\partial^t_{\mathrm v}\Omega|^2/t^2}\).” The authors prove (Theorem 3) that, if \(k\geq 2\), then \(|\partial_{\mathrm v}\Omega|\leq \frac{C}{k} |\partial_{\mathrm h}\Omega|\) for some absolute constant \(C\). They emphasize that, for \(k=1\), the results are different; these results will be presented in a separate paper whose short description is provided in an ‘Added in proof’ note.
The proof of these very impressive results contains many sophisticated steps and cannot be outlined here. I refer the readers to the ‘Roadmap’ on pages 185–186 of the paper, I would only like to mention that the proof of Theorem 3 takes place in a setting of ‘continuous’ Heisenberg groups.

Reviewer: Mikhail Ostrovskii (Queens)

MSC:

46B85	Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science
20F65	Geometric group theory
30L05	Geometric embeddings of metric spaces
43A15	\(L^p\)-spaces and other function spaces on groups, semigroups, etc.
68W25	Approximation algorithms

Keywords:

approximation algorithm; Heisenberg group; isoperimetric inequality; metric embedding; metric of negative type; semidefinite programming; sparsest cut problem

Citations:

Zbl 0696.68071; Zbl 0887.90139; Zbl 1132.68070; Zbl 1247.46020

References:

[1]	Ambrosio, Luigi; Fusco, Nicola; Pallara, Diego, Functions of Bounded Variation and Free Discontinuity Problems, Oxford Math. Monogr., xviii+434 pp., (2000) · Zbl 0957.49001
[2]	Klein, Philip; Agrawal, Ajit; Ravi, R.; Rao, Satish, Approximation through multicommodity flow. 31st {A}nnual {S}ymposium on {F}oundations of {C}omputer {S}cience, {V}ol.{I}, {II}, 726-737, (1990)
[3]	Arora, Sanjeev; Lee, James R.; Naor, Assaf, Euclidean distortion and the sparsest cut, J. Amer. Math. Soc.. Journal of the Amer. Math. Soc., 21, 1-21, (2008) · Zbl 1132.68070
[4]	Ambrosio, Luigi, Some fine properties of sets of finite perimeter in {A}hlfors regular metric measure spaces, Adv. Math.. Advances in Mathematics, 159, 51-67, (2001) · Zbl 1002.28004
[5]	Andoni, A.; Naor, A.; Neiman, O., Snowflake universality of {W}asserstein spaces, (2015) · Zbl 1403.46020
[6]	Austin, Tim; Naor, Assaf; Tessera, Romain, Sharp quantitative nonembeddability of the {H}eisenberg group into superreflexive {B}anach spaces, Groups Geom. Dyn.. Groups, Geometry, and Dynamics, 7, 497-522, (2013) · Zbl 1284.46019
[7]	Aumann, Yonatan; Rabani, Yuval, An {\(O(\log k)\)} approximate min-cut max-flow theorem and approximation algorithm, SIAM J. Comput.. SIAM Journal on Computing, 27, 291-301, (1998) · Zbl 0910.05038
[8]	Arora, Sanjeev; Rao, Satish; Vazirani, Umesh, Expander flows, geometric embeddings and graph partitioning, J. ACM. Journal of the ACM, 56, 5-37, (2009) · Zbl 1325.68255
[9]	Assouad, Patrice, Plongements lipschitziens dans {\(\textbf{R}\sp{n}\)}, Bull. Soc. Math. France. Bulletin de la Soci\'et\'e Math\'ematique de France, 111, 429-448, (1983) · Zbl 0597.54015
[10]	Ball, K., Markov chains, {R}iesz transforms and {L}ipschitz maps, Geom. Funct. Anal.. Geometric and Functional Analysis, 2, 137-172, (1992) · Zbl 0788.46050
[11]	Ball, Keith, The {R}ibe programme. S\'eminaire Bourbaki. Vol. 2011/2012. Expos\'es 1043–1058, Ast\'erisque, 352, 147-159, (2013)
[12]	Bass, H., The degree of polynomial growth of finitely generated nilpotent groups, Proc. London Math. Soc. (3). Proceedings of the London Mathematical Society. Third Series, 25, 603-614, (1972) · Zbl 0259.20045
[13]	Burago, Dmitri; Burago, Yuri; Ivanov, Sergei, A Course in Metric Geometry, Grad. Studies in Math., 33, xiv+415 pp., (2001) · Zbl 0981.51016
[14]	Benyamini, Yoav; Lindenstrauss, Joram, Geometric Nonlinear Functional Analysis. {V}ol. 1, Amer. Math. Soc. Colloq. Publ., 48, xii+488 pp., (2000) · Zbl 0946.46002
[15]	Baudier, F.; Lancien, G., Embeddings of locally finite metric spaces into {B}anach spaces, Proc. Amer. Math. Soc.. Proceedings of the Amer. Math. Soc., 136, 1029-1033, (2008) · Zbl 1142.46037
[16]	Blach\`“‘ere, S\'”’ebastien, Word distance on the discrete {H}eisenberg group, Colloq. Math.. Colloquium Mathematicum, 95, 21-36, (2003) · Zbl 1010.05034
[17]	Bourgain, J., On {L}ipschitz embedding of finite metric spaces in {H}ilbert space, Israel J. Math.. Israel Journal of Mathematics, 52, 46-52, (1985) · Zbl 0657.46013
[18]	Bourgain, J., On the distributions of the {F}ourier spectrum of {B}oolean functions, Israel J. Math.. Israel Journal of Mathematics, 131, 269-276, (2002) · Zbl 1021.43004
[19]	Brunel, Antoine; Sucheston, Louis, Sur quelques conditions \'equivalentes \`“‘a la super-r\'”’eflexivit\'e dans les espaces de {B}anach, C. R. Acad. Sci. Paris S\'er. A-B, 275, A993-A994, (1972) · Zbl 0245.46016
[20]	Chawla, Shuchi; Gupta, Anupam; R\"acke, Harald, Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut, ACM Trans. Algorithms. ACM Transactions on Algorithms, 4, 22-18, (2008) · Zbl 1297.68234
[21]	Chawla, Shuchi, Sparsest cut. Encyclopedia of Algorithms, 868-870, (2008)
[22]	Christ, Michael, A {\(T(b)\)} theorem with remarks on analytic capacity and the {C}auchy integral, Colloq. Math.. Colloquium Mathematicum, 60/61, 601-628, (1990) · Zbl 0758.42009
[23]	Cheeger, Jeff; Kleiner, Bruce, On the differentiability of {L}ipschitz maps from metric measure spaces to {B}anach spaces. Inspired by {S}. {S}. {C}hern, Nankai Tracts Math., 11, 129-152, (2006) · Zbl 1139.58004
[24]	Chuzhoy, Julia; Khanna, Sanjeev, Polynomial flow-cut gaps and hardness of directed cut problems [extended abstract]. S{TOC}’07—{P}roceedings of the 39th {A}nnual {ACM} {S}ymposium on {T}heory of {C}omputing, 179-188, (2007) · Zbl 1232.68063
[25]	Chuzhoy, Julia; Khanna, Sanjeev, Polynomial flow-cut gaps and hardness of directed cut problems, J. ACM. Journal of the ACM, 56, 6-28, (2009) · Zbl 1325.68096
[26]	Cheeger, Jeff; Kleiner, Bruce, Differentiating maps into {\(L^1\)}, and the geometry of {BV} functions, Ann. of Math. (2). Annals of Mathematics. Second Series, 171, 1347-1385, (2010) · Zbl 1194.22009
[27]	Cheeger, Jeff; Kleiner, Bruce, Metric differentiation, monotonicity and maps to {\(L^1\)}, Invent. Math.. Inventiones Mathematicae, 182, 335-370, (2010) · Zbl 1214.46013
[28]	Chawla, Shuchi; Krauthgamer, Robert; Kumar, Ravi; Rabani, Yuval; Sivakumar, D., On the hardness of approximating multicut and sparsest-cut, Comput. Complexity. Computational Complexity, 15, 94-114, (2006) · Zbl 1132.68418
[29]	Cheeger, Jeff; Kleiner, Bruce; Naor, Assaf, A {\((\log n)^{\Omega(1)}\)} integrality gap for the sparsest cut {SDP}. 2009 50th {A}nnual {IEEE} {S}ymposium on {F}oundations of {C}omputer {S}cience—{FOCS} 2009, 555-564, (2009) · Zbl 1291.90318
[30]	Cheeger, Jeff; Kleiner, Bruce; Naor, Assaf, Compression bounds for {L}ipschitz maps from the {H}eisenberg group to {\(L_1\)}, Acta Math.. Acta Mathematica, 207, 291-373, (2011) · Zbl 1247.46020
[31]	David, Guy, Op\'erateurs int\'egraux singuliers sur certaines courbes du plan complexe, Ann. Sci. \'Ecole Norm. Sup. (4). Annales Scientifiques de l’\'Ecole Normale Sup\'erieure. Quatri\`“‘eme S\'”’erie, 17, 157-189, (1984) · Zbl 0537.42016
[32]	David, Guy, Wavelets and Singular Integrals on Curves and Surfaces, Lecture Notes in Math., 1465, x+107 pp., (1991) · Zbl 0764.42019
[33]	Devanur, Nikhil R.; Khot, Subhash A.; Saket, Rishi; Vishnoi, Nisheeth K., Integrality gaps for sparsest cut and minimum linear arrangement problems. S{TOC}’06: {P}roceedings of the 38th {A}nnual {ACM} {S}ymposium on {T}heory of {C}omputing, 537-546, (2006) · Zbl 1301.05332
[34]	Deza, Michel Marie; Laurent, Monique, Geometry of Cuts and Metrics, Algorithms Combin., 15, xii+587 pp., (1997) · Zbl 1210.52001
[35]	Ding, Jian; Lee, James R.; Peres, Yuval, Markov type and threshold embeddings, Geom. Funct. Anal.. Geometric and Functional Analysis, 23, 1207-1229, (2013) · Zbl 1279.46013
[36]	David, G.; Semmes, S., Singular integrals and rectifiable sets in {\(\textbf{R}^n\)}: {B}eyond {L}ipschitz graphs, Ast\'erisque. Ast\'erisque, 193, 152 pp. pp., (1991)
[37]	David, Guy; Semmes, Stephen, Analysis of and on Uniformly Rectifiable Sets, Math. Surveys Monogr., 38, xii+356 pp., (1993) · Zbl 0832.42008
[38]	Franchi, Bruno; Serapioni, Raul; Serra Cassano, Francesco, Meyers-{S}errin type theorems and relaxation of variational integrals depending on vector fields, Houston J. Math.. Houston Journal of Mathematics, 22, 859-890, (1996) · Zbl 0876.49014
[39]	Franchi, Bruno; Serapioni, Raul; Serra Cassano, Francesco, Rectifiability and perimeter in the {H}eisenberg group, Math. Ann.. Mathematische Annalen, 321, 479-531, (2001) · Zbl 1057.49032
[40]	Franchi, Bruno; Serapioni, Raul; Serra Cassano, Francesco, On the structure of finite perimeter sets in step 2 {C}arnot groups, J. Geom. Anal.. The Journal of Geometric Analysis, 13, 421-466, (2003) · Zbl 1064.49033
[41]	Franchi, Bruno; Serapioni, Raul; Serra Cassano, Francesco, Intrinsic {L}ipschitz graphs in {H}eisenberg groups, J. Nonlinear Convex Anal.. Journal of Nonlinear and Convex Analysis. An International Journal, 7, 423-441, (2006) · Zbl 1151.58005
[42]	Franchi, Bruno; Serapioni, Raul; Serra Cassano, Francesco, Differentiability of intrinsic {L}ipschitz functions within {H}eisenberg groups, J. Geom. Anal.. Journal of Geometric Analysis, 21, 1044-1084, (2011) · Zbl 1234.22002
[43]	Gupta, Anupam; Krauthgamer, Robert; Lee, James R., Bounded geometries, fractals, and low-distortion embeddings. FOCS ’03 Proceedings of the 44th Symposium on Foundations of Computer Science, 534-543, (2003)
[44]	Gr\`“otschel, Martin; Lov\'”asz, L\'aszl\'o; Schrijver, Alexander, Geometric Algorithms and Combinatorial Optimization, Algorithms Combin., 2, xii+362 pp., (1993) · Zbl 0837.05001
[45]	Garofalo, Nicola; Nhieu, Duy-Minh, Isoperimetric and {S}obolev inequalities for {C}arnot-{C}arath\'eodory spaces and the existence of minimal surfaces, Comm. Pure Appl. Math.. Communications on Pure and Applied Mathematics, 49, 1081-1144, (1996) · Zbl 0880.35032
[46]	Goemans, Michel X., Semidefinite programming in combinatorial optimization, Math. Programming. Mathematical Programming, 79, 143-161, (1997) · Zbl 0887.90139
[47]	Gromov, Mikhael, Groups of polynomial growth and expanding maps, Inst. Hautes \'Etudes Sci. Publ. Math.. Institut des Hautes \'Etudes Scientifiques. Publications Math\'ematiques, 53, 53-73, (1981) · Zbl 0474.20018
[48]	Gromov, Mikhael, Carnot-{C}arath\'eodory spaces seen from within. Sub-{R}iemannian Geometry, Progr. Math., 144, 79-323, (1996) · Zbl 0864.53025
[49]	Heinrich, Stefan, Ultraproducts in {B}anach space theory, J. Reine Angew. Math.. Journal f\"ur die Reine und Angewandte Mathematik, 313, 72-104, (1980) · Zbl 0412.46017
[50]	Haj{\l}asz, Piotr; Koskela, Pekka, Sobolev met {P}oincar\'e, Mem. Amer. Math. Soc.. Memoirs of the Amer. Math. Soc., 145, x+101 pp., (2000) · Zbl 0954.46022
[51]	Jaffe, Alexander; Lee, James R.; Moharrami, Mohammad, On the optimality of gluing over scales, Discrete Comput. Geom.. Discrete & Computational Geometry. An International Journal of Mathematics and Computer Science, 46, 270-282, (2011) · Zbl 1219.68159
[52]	Jones, Peter W., Square functions, {C}auchy integrals, analytic capacity, and harmonic measure. Harmonic Analysis and Partial Differential Equations, Lecture Notes in Math., 1384, 24-68, (1989)
[53]	Jones, Peter W., Rectifiable sets and the traveling salesman problem, Invent. Math.. Inventiones Mathematicae, 102, 1-15, (1990) · Zbl 0731.30018
[54]	Kadec, M. I., Linear dimension of the spaces {\(L\sb{p}\)} and {\(l\sb{q}\)}, Uspehi Mat. Nauk. Akademiya Nauk SSSR i Moskovskoe Matematicheskoe Obshchestvo. Uspekhi Matematicheskikh Nauk, 13, 95-98, (1958) · Zbl 0087.10802
[55]	Khot, Subhash, On the power of unique 2-prover 1-round games. Proceedings of the {T}hirty-{F}ourth {A}nnual {ACM} {S}ymposium on {T}heory of {C}omputing, 767-775, (2002) · Zbl 1192.68367
[56]	Khot, Subhash, Inapproximability of {NP}-complete problems, discrete {F}ourier analysis, and geometry. Proceedings of the {I}nternational {C}ongress of {M}athematicians 2010 (ICM 2010). {V}olume {IV}, 2676-2697, (2012) · Zbl 1252.68143
[57]	Kirchheim, Bernd, Rectifiable metric spaces: local structure and regularity of the {H}ausdorff measure, Proc. Amer. Math. Soc.. Proceedings of the Amer. Math. Soc., 121, 113-123, (1994) · Zbl 0806.28004
[58]	Kahn, Jeff; Kalai, Gil; Linial, Nathan, The influence of variables on {B}oolean functions (extended abstract). 29th Annual Symposium on Foundations of Computer Science, 68-80, (1988)
[59]	Kleiner, Bruce, A new proof of {G}romov’s theorem on groups of polynomial growth, J. Amer. Math. Soc.. Journal of the Amer. Math. Soc., 23, 815-829, (2010) · Zbl 1246.20038
[60]	Krauthgamer, R.; Lee, J. R.; Mendel, M.; Naor, A., Measured descent: a new embedding method for finite metrics, Geom. Funct. Anal.. Geometric and Functional Analysis, 15, 839-858, (2005) · Zbl 1108.46010
[61]	Kane, Daniel; Meka, Raghu, A {PRG} for {L}ipschitz functions of polynomials with applications to sparsest cut. S{TOC}’13—{P}roceedings of the 2013 {ACM} {S}ymposium on {T}heory of {C}omputing, 1-10, (2013) · Zbl 1293.65007
[62]	Khot, Subhash; Naor, Assaf, Nonembeddability theorems via {F}ourier analysis, Math. Ann.. Mathematische Annalen, 334, 821-852, (2006) · Zbl 1102.46051
[63]	Krauthgamer, Robert; Rabani, Yuval, Improved lower bounds for embeddings into {\(L_1\)}, SIAM J. Comput.. SIAM Journal on Computing, 38, 2487-2498, (2009) · Zbl 1191.68869
[64]	Khot, Subhash A.; Vishnoi, Nisheeth K., The unique games conjecture, integrability gap for cut problems and embeddability of negative-type metrics into {\(\ell_1\)}, J. ACM. Journal of the ACM, 62, 8-39, (2015) · Zbl 1321.68316
[65]	Lee, James R., On distance scales, embeddings, and efficient relaxations of the cut cone. Proceedings of the {S}ixteenth {A}nnual {ACM}-{SIAM} {S}ymposium on {D}iscrete {A}lgorithms, 92-101, (2005) · Zbl 1297.68244
[66]	Li, Sean, Coarse differentiation and quantitative nonembeddability for {C}arnot groups, J. Funct. Anal.. Journal of Functional Analysis, 266, 4616-4704, (2014) · Zbl 1311.46021
[67]	Li, Sean, Markov convexity and nonembeddability of the {H}eisenberg group, Ann. Inst. Fourier (Grenoble). Universit\'e de Grenoble. Annales de l’Institut Fourier, 66, 1615-1651, (2016) · Zbl 1439.30087
[68]	Linial, Nathan, Finite metric-spaces—combinatorics, geometry and algorithms. Proceedings of the {I}nternational {C}ongress of {M}athematicians, {V}ol. {III}, 573-586, (2002) · Zbl 0997.05019
[69]	Linial, Nathan, Squared \(\ell_2\) metrics into \(\ell_1\). Open Problems on Embeddings of Finite Metric Spaces, 5 pp., (2002)
[70]	Linial, Nathan; London, Eran; Rabinovich, Yuri, The geometry of graphs and some of its algorithmic applications, Combinatorica. Combinatorica. An International Journal on Combinatorics and the Theory of Computing, 15, 215-245, (1995) · Zbl 0827.05021
[71]	Lee, James R.; Mendel, Manor; Naor, Assaf, Metric structures in {\(L_1\)}: dimension, snowflakes, and average distortion, European J. Combin.. European Journal of Combinatorics, 26, 1180-1190, (2005) · Zbl 1106.68086
[72]	Lee, James R.; Naor, Assaf, \({L}_p\) metrics on the {H}eisenberg group and the {G}oemans-{L}inial conjecture. Proceedings of 47th Annual IEEE Symposium on Foundations of Computer Science, 99-108, (2006)
[73]	Lafforgue, Vincent; Naor, Assaf, A doubling subset of {\(L_p\)} for {\(p>2\)} that is inherently infinite dimensional, Geom. Dedicata. Geometriae Dedicata, 172, 387-398, (2014) · Zbl 1305.30029
[74]	Lafforgue, Vincent; Naor, Assaf, Vertical versus horizontal {P}oincar\'e inequalities on the {H}eisenberg group, Israel J. Math.. Israel Journal of Mathematics, 203, 309-339, (2014) · Zbl 1312.46032
[75]	Lee, James R.; Naor, Assaf; Peres, Yuval, Trees and {M}arkov convexity, Geom. Funct. Anal.. Geometric and Functional Analysis, 18, 1609-1659, (2009) · Zbl 1171.05318
[76]	Leighton, Tom; Rao, Satish, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, J. ACM. Journal of the ACM, 46, 787-832, (1999) · Zbl 1065.68666
[77]	Lee, James R.; Sidiropoulos, Anastasios, Near-optimal distortion bounds for embedding doubling spaces into {\(L_1\)} [extended abstract]. S{TOC}’11—{P}roceedings of the 43rd {ACM} {S}ymposium on {T}heory of {C}omputing, 765-772, (2011) · Zbl 1288.90079
[78]	Matou{\v{s}}ek, Ji{\v{r}}{\'{\i}}, Lectures on Discrete Geometry, Grad. Texts in Math., 212, xvi+481 pp., (2002) · Zbl 0999.52006
[79]	Maurey, Bernard, Type, cotype and {\(K\)}-convexity. Handbook of the Geometry of {B}anach Sspaces, {V}ol.2, 1299-1332, (2003) · Zbl 1074.46006
[80]	McShane, E. J., Extension of range of functions, Bull. Amer. Math. Soc.. Bulletin of the Amer. Math. Soc., 40, 837-842, (1934) · Zbl 0010.34606
[81]	Mendel, Manor, Metric dichotomies. Limits of Graphs in Group Theory and Computer Science, 59-76, (2009) · Zbl 1293.05386
[82]	Makarychev, Konstantin; Makarychev, Yury; Vijayaraghavan, Aravindan, Bilu-{L}inial stable instances of max cut and minimum multiway cut. Proceedings of the {T}wenty-{F}ifth {A}nnual {ACM}-{SIAM} {S}ymposium on {D}iscrete {A}lgorithms, 890-906, (2014) · Zbl 1422.68127
[83]	Mendel, Manor; Naor, Assaf, A note on dichotomies for metric transforms, (2011) · Zbl 1218.46012
[84]	Mendel, Manor; Naor, Assaf, Markov convexity and local rigidity of distorted metrics, J. Eur. Math. Soc. (JEMS). Journal of the European Mathematical Society (JEMS), 15, 287-337, (2013) · Zbl 1266.46016
[85]	Montgomery, Richard, A {T}our of {S}ubriemannian {G}eometries, {T}heir {G}eodesics and {A}pplications, Math. Surveys Monogr., 91, xx+259 pp., (2002) · Zbl 1044.53022
[86]	Montefalcone, Francescopaolo, Some relations among volume, intrinsic perimeter and one-dimensional restrictions of {BV} functions in {C}arnot groups, Ann. Sc. Norm. Super. Pisa Cl. Sci. (5). Annali della Scuola Normale Superiore di Pisa. Classe di Scienze. Serie V, 4, 79-128, (2005) · Zbl 1150.49022
[87]	Maurey, Bernard; Pisier, Gilles, S\'eries de variables al\'eatoires vectorielles ind\'ependantes et propri\'et\'es g\'eom\'etriques des espaces de {B}anach, Studia Math.. Polska Akademia Nauk. Instytut Matematyczny. Studia Mathematica, 58, 45-90, (1976) · Zbl 0344.47014
[88]	Mart{\'{\i}}nez, Teresa; Torrea, Jos\'e L.; Xu, Quanhua, Vector-valued {L}ittlewood-{P}aley-{S}tein theory for semigroups, Adv. Math.. Advances in Mathematics, 203, 430-475, (2006) · Zbl 1111.46008
[89]	Milman, V. D.; Wolfson, H., Minkowski spaces with extremal distance from the {E}uclidean space, Israel J. Math.. Israel Journal of Mathematics, 29, 113-131, (1978) · Zbl 0374.46013
[90]	Naor, Assaf, {\(L_1\)} embeddings of the {H}eisenberg group and fast estimation of graph isoperimetry. Proceedings of the {I}nternational {C}ongress of {M}athematicians. {V}olume {III}, 1549-1575, (2010) · Zbl 1232.46021
[91]	Naor, Assaf, An introduction to the {R}ibe program, Jpn. J. Math.. Japanese Journal of Mathematics, 7, 167-233, (2012) · Zbl 1261.46013
[92]	Naor, Assaf, Comparison of metric spectral gaps, Anal. Geom. Metr. Spaces. Analysis and Geometry in Metric Spaces, 2, 1-52, (2014) · Zbl 1316.46023
[93]	Naor, Assaf; Peres, Yuval; Schramm, Oded; Sheffield, Scott, Markov chains in smooth {B}anach spaces and {G}romov-hyperbolic metric spaces, Duke Math. J.. Duke Mathematical Journal, 134, 165-197, (2006) · Zbl 1108.46012
[94]	Naor, Assaf; Rabani, Yuval; Sinclair, Alistair, Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs, J. Funct. Anal.. Journal of Functional Analysis, 227, 273-303, (2005) · Zbl 1104.68087
[95]	Naor, Assaf; Silberman, Lior, Poincar\'e inequalities, embeddings, and wild groups, Compos. Math.. Compositio Mathematica, 147, 1546-1572, (2011) · Zbl 1267.20057
[96]	Naor, Assaf; Young, Robert, Foliated corona decompositions and the \({L}_1\) distortion of balls in the \(3\)-dimensional {H}eisenberg group · Zbl 1370.68235
[97]	Naor, Assaf; Young, Robert, The integrality gap of the {G}oemans-{L}inial {SDP} relaxation for sparsest cut is at least a constant multiple of {\(\sqrt{\log n}\)}. S{TOC}’17—{P}roceedings of the 49th {A}nnual {ACM} {SIGACT} {S}ymposium on {T}heory of {C}omputing, 564-575, (2017) · Zbl 1276.46013
[98]	Ostrovskii, M. I., Embeddability of locally finite metric spaces into {B}anach spaces is finitely determined, Proc. Amer. Math. Soc.. Proceedings of the Amer. Math. Soc., 140, 2721-2730, (2012) · Zbl 1279.46001
[99]	Ostrovskii, Mikhail I., Metric Embeddings, De Gruyter Stud. Math., 49, xii+372 pp., (2013) · Zbl 0502.53039
[100]	Pansu, Pierre, Une in\'egalit\'e isop\'erim\'etrique sur le groupe de {H}eisenberg, C. R. Acad. Sci. Paris S\'er. I Math.. Comptes Rendus des S\'eances de l’Acad\'emie des Sciences. S\'erie I. Math\'ematique, 295, 127-130, (1982) · Zbl 0678.53042
[101]	Pansu, Pierre, M\'etriques de {C}arnot-{C}arath\'eodory et quasiisom\'etries des espaces sym\'etriques de rang un, Ann. of Math. (2). Annals of Mathematics. Second Series, 129, 1-60, (1989) · Zbl 0344.46030
[102]	Pisier, Gilles, Martingales with values in uniformly convex spaces, Israel J. Math.. Israel Journal of Mathematics, 20, 326-350, (1975) · Zbl 1046.46048
[103]	Pisier, Gilles; Xu, Quanhua, Non-commutative {\(L^p\)}-{S}paces. Handbook of the Geometry of {B}anach spaces, {V}ol.2, 1459-1517, (2003) · Zbl 1046.46048
[104]	Rao, Satish, Small distortion and volume preserving embeddings for planar and {E}uclidean metrics. Proceedings of the {F}ifteenth {A}nnual {S}ymposium on {C}omputational {G}eometry, 300-306, (1999)
[105]	Shmoys, D. B., Cut problems and their application to divide-and-conquer. Approximation Algorithms for \(\text{NP}\)-hard Problems, 192-235, (1997) · Zbl 0668.05060
[106]	Sinclair, Alistair; Jerrum, Mark, Approximate counting, uniform generation and rapidly mixing {M}arkov chains, Inform. and Comput.. Information and Computation, 82, 93-133, (1989) · Zbl 0696.68071
[107]	Shahrokhi, Farhad; Matula, D. W., The maximum concurrent flow problem, J. Assoc. Comput. Mach.. Journal of the Association for Computing Machinery, 37, 318-334, (1990) · Zbl 1162.46043
[108]	Tessera, Romain, Quantitative property {A}, {P}oincar\'e inequalities, {\(L^p\)}-compression and {\(L^p\)}-distortion for metric measure spaces, Geom. Dedicata. Geometriae Dedicata, 136, 203-220, (2008) · Zbl 1280.68102
[109]	Trevisan, Luca, On {K}hot’s unique games conjecture, Bull. Amer. Math. Soc. (N.S.). Amer. Math. Soc.. Bulletin. New Series, 49, 91-111, (2012) · Zbl 0724.46012
[110]	Wojtaszczyk, P., Banach Spaces for Analysts, Cambridge Stud. Adv. Math., 25, xiv+382 pp., (1991) · Zbl 0724.46012
[111]	Wells, J. H.; Williams, L. R., Embeddings and Extensions in Analysis, 84, vii+108 pp., (1975) · Zbl 1391.49081