Vertical perimeter versus horizontal perimeter

Abstract

Given $k\in \mathbb {N}$, the $k$’th discrete Heisenberg group, denoted $ \mathbb {H}_{\scriptscriptstyle {\mathbb {Z}}}^{2k+1}$, is the group generated by the elements $a_1,b_1,\ldots ,a_k,b_k,c$, subject to the commutator relations $[a_1,b_1]=\cdots =[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,…,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}_{ \scriptscriptstyle { \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 \subseteq \mathbb {H}_{ \scriptscriptstyle { \mathbb {Z}}}^{2k+1}$, denoted $\partial _{\mathsf {h}}\Omega $, is the set of all those pairs $(x,y)\in \Omega \times ( \mathbb {H}_{ \scriptscriptstyle { \mathbb {Z}}}^{2k+1}\smallsetminus \Omega )$ such that $x^{-1}y\in \mathfrak {S}_k$. The horizontal perimeter of $\Omega $ is the cardinality $|\partial _{\mathsf {h}}\Omega |$ of $\partial _{\mathsf {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_{\mathsf {v}} \Omega $ to be the set of all those pairs $(x,y)\in \Omega \times ( \mathbb {H}_{ \scriptscriptstyle { \mathbb {Z}}}^{2k+1}\smallsetminus \Omega )$ such that $x^{-1}y\in \{c^t,c^{-t}\}$. Thus, $|\partial ^t_{\mathsf {v}}\Omega |$ is the total number of edges incident to $\Omega $ in the (disconnected) Cayley graph induced by $\{c^t,c^{-t}\}\subseteq \mathbb {H}_{ \scriptscriptstyle { \mathbb {Z}}}^{2k+1}$. The vertical perimeter of $\Omega $ is defined by $|\partial _{\mathsf {v}}\Omega |= \sqrt { \sum_{t=1}^\infty |\partial ^t_{\mathsf {v}}\Omega |^2/t^2}$. It is shown here that if $k\geqslant 2$, then $|\partial _{\mathsf {v}}\Omega |\lesssim \frac {1}{k} |\partial _{\mathsf {h}}\Omega |$. The proof of this “vertical versus horizontal isoperimetric inequality” uses a new structural result that decomposes sets of finite perimeter in the Heisenberg group into pieces that admit an “intrinsic corona decomposition.” This allows one to deduce an endpoint $W^{1,1}\to L_2(L_1)$ boundedness of a certain singular integral operator from a corresponding lower-dimensional $W^{1,2}\to L_2(L_2)$ boundedness. Apart from its intrinsic geometric interest, the above (sharp) isoperimetric-type inequality has several (sharp) applications, including that for every $n\in \mathbb {N}$, any embedding into an $L_1(\mu)$ space of a ball of radius $n$ in the word metric on $ \mathbb {H}_{ \scriptscriptstyle { \mathbb {Z}}}^{5}$ that is induced by the generating set $\mathfrak {S}_2$ incurs bi-Lipschitz distortion that is at least a universal constant multiple of $\sqrt{\log n}$. As an application to approximation algorithms, it follows that for every $n\in \mathbb {N}$, the integrality gap of the Goemans–Linial semidefinite program for the Sparsest Cut Problem on inputs of size $n$ is at least a universal constant multiple of $\sqrt{\log n}$.

  • [AmbFuscPall] L. Ambrosio, N. Fusco, and D. Pallara, Functions of Bounded Variation and Free Discontinuity Problems, The Clarendon Press, Oxford University Press, New York, 2000.
    @BOOK{AmbFuscPall,
      author = {Ambrosio, Luigi and Fusco, Nicola and Pallara, Diego},
      title = {Functions of Bounded Variation and Free Discontinuity Problems},
      series = {Oxford Math. Monogr.},
      publisher = {The Clarendon Press, Oxford University Press, New York},
      year = {2000},
      pages = {xviii+434},
      isbn = {0-19-850245-1},
      mrclass = {49-02 (49J45 49K10 49Qxx)},
      mrnumber = {1857292},
      mrreviewer = {J. E. Brothers},
      zblnumber = {0957.49001},
      }
  • [AKRR90] Go to document P. Klein, A. Agrawal, R. Ravi, and S. Rao, "Approximation through multicommodity flow," in 31st Annual Symposium on Foundations of Computer Science, Vol. I, II, IEEE Comput. Soc. Press, Los Alamitos, CA, 1990, pp. 726-737.
    @INCOLLECTION{AKRR90,
      author = {Klein, Philip and Agrawal, Ajit and Ravi, R. and Rao, Satish},
      title = {Approximation through multicommodity flow},
      booktitle = {31st {A}nnual {S}ymposium on {F}oundations of {C}omputer {S}cience, {V}ol. {I},
      {II}},
      venue = {{S}t. {L}ouis, {MO},
      1990},
      pages = {726--737},
      publisher = {IEEE Comput. Soc. Press, Los Alamitos, CA},
      year = {1990},
      mrclass = {90B10 (68R10)},
      mrnumber = {1150728},
      doi = {10.1109/FSCS.1990.89595},
      zblnumber = {},
      }
  • [ALN08] Go to document S. Arora, J. R. Lee, and A. Naor, "Euclidean distortion and the sparsest cut," J. Amer. Math. Soc., vol. 21, iss. 1, pp. 1-21, 2008.
    @ARTICLE{ALN08,
      author = {Arora, Sanjeev and Lee, James R. and Naor, Assaf},
      title = {Euclidean distortion and the sparsest cut},
      journal = {J. Amer. Math. Soc.},
      fjournal = {Journal of the Amer. Math. Soc.},
      volume = {21},
      year = {2008},
      number = {1},
      pages = {1--21},
      issn = {0894-0347},
      mrclass = {51F99 (46B07 68W25 90C90)},
      mrnumber = {2350049},
      mrreviewer = {Florent Baudier},
      doi = {10.1090/S0894-0347-07-00573-5},
      zblnumber = {1132.68070},
      }
  • [AmbrosioFineProperties] Go to document L. Ambrosio, "Some fine properties of sets of finite perimeter in Ahlfors regular metric measure spaces," Adv. Math., vol. 159, iss. 1, pp. 51-67, 2001.
    @ARTICLE{AmbrosioFineProperties,
      author = {Ambrosio, Luigi},
      title = {Some fine properties of sets of finite perimeter in {A}hlfors regular metric measure spaces},
      journal = {Adv. Math.},
      fjournal = {Advances in Mathematics},
      volume = {159},
      year = {2001},
      number = {1},
      pages = {51--67},
      issn = {0001-8708},
      mrclass = {31A15 (28A75 28C99 35J15)},
      mrnumber = {1823840},
      mrreviewer = {Vladimir N. Dubinin},
      doi = {10.1006/aima.2000.1963},
      zblnumber = {1002.28004},
      }
  • [ANN15] A. Andoni, A. Naor, and O. Neiman, Snowflake universality of Wasserstein spaces, 2015.
    @MISC{ANN15,
      author = {Andoni, A. and Naor, A. and Neiman, O.},
      title = {Snowflake universality of {W}asserstein spaces},
      arxiv = {1509.08677},
      year = {2015},
      zblnumber = {},
      }
  • [AusNaoTes] Go to document T. Austin, A. Naor, and R. Tessera, "Sharp quantitative nonembeddability of the Heisenberg group into superreflexive Banach spaces," Groups Geom. Dyn., vol. 7, iss. 3, pp. 497-522, 2013.
    @ARTICLE{AusNaoTes,
      author = {Austin, Tim and Naor, Assaf and Tessera, Romain},
      title = {Sharp quantitative nonembeddability of the {H}eisenberg group into superreflexive {B}anach spaces},
      journal = {Groups Geom. Dyn.},
      fjournal = {Groups, Geometry, and Dynamics},
      volume = {7},
      year = {2013},
      number = {3},
      pages = {497--522},
      issn = {1661-7207},
      mrclass = {46B85 (20F65 30L05)},
      mrnumber = {3095705},
      mrreviewer = {Florent Baudier},
      doi = {10.4171/GGD/193},
      zblnumber = {1284.46019},
      }
  • [AR98] Go to document Y. Aumann and Y. Rabani, "An $O(\log k)$ approximate min-cut max-flow theorem and approximation algorithm," SIAM J. Comput., vol. 27, iss. 1, pp. 291-301, 1998.
    @ARTICLE{AR98,
      author = {Aumann, Yonatan and Rabani, Yuval},
      title = {An {$O(\log k)$} approximate min-cut max-flow theorem and approximation algorithm},
      journal = {SIAM J. Comput.},
      fjournal = {SIAM Journal on Computing},
      volume = {27},
      year = {1998},
      number = {1},
      pages = {291--301},
      issn = {0097-5397},
      mrclass = {05C85 (68R10 90B10)},
      mrnumber = {1614825},
      mrreviewer = {Michal Penn},
      doi = {10.1137/S0097539794285983},
      zblnumber = {0910.05038},
      }
  • [ARV09] Go to document S. Arora, S. Rao, and U. Vazirani, "Expander flows, geometric embeddings and graph partitioning," J. ACM, vol. 56, iss. 2, p. 5, 2009.
    @ARTICLE{ARV09,
      author = {Arora, Sanjeev and Rao, Satish and Vazirani, Umesh},
      title = {Expander flows, geometric embeddings and graph partitioning},
      journal = {J. ACM},
      fjournal = {Journal of the ACM},
      volume = {56},
      year = {2009},
      number = {2},
      pages = {Art. 5, 37},
      issn = {0004-5411},
      mrclass = {68R10 (05C85 60D05 68W25)},
      mrnumber = {2535878},
      doi = {10.1145/1502793.1502794},
      zblnumber = {1325.68255},
      }
  • [Ass83] Go to document P. Assouad, "Plongements lipschitziens dans ${\bf R}^{n}$," Bull. Soc. Math. France, vol. 111, iss. 4, pp. 429-448, 1983.
    @ARTICLE{Ass83,
      author = {Assouad, Patrice},
      title = {Plongements lipschitziens dans {${\bf R}\sp{n}$}},
      journal = {Bull. Soc. Math. France},
      fjournal = {Bulletin de la Société Mathématique de France},
      volume = {111},
      year = {1983},
      number = {4},
      pages = {429--448},
      issn = {0037-9484},
      mrclass = {54E40 (54F45)},
      mrnumber = {0763553},
      mrreviewer = {S. J. Taylor},
      doi = {10.24033/bsmf.1997},
      zblnumber = {0597.54015},
      }
  • [Bal92] Go to document K. Ball, "Markov chains, Riesz transforms and Lipschitz maps," Geom. Funct. Anal., vol. 2, iss. 2, pp. 137-172, 1992.
    @ARTICLE{Bal92,
      author = {Ball, K.},
      title = {Markov chains, {R}iesz transforms and {L}ipschitz maps},
      journal = {Geom. Funct. Anal.},
      fjournal = {Geometric and Functional Analysis},
      volume = {2},
      year = {1992},
      number = {2},
      pages = {137--172},
      issn = {1016-443X},
      mrclass = {46B20 (47B99 47H99 60J10)},
      mrnumber = {1159828},
      mrreviewer = {Aleksandr Koldobsky},
      doi = {10.1007/BF01896971},
      zblnumber = {0788.46050},
      }
  • [Bal13] K. Ball, "The Ribe programme," in Séminaire Bourbaki. Vol. 2011/2012. Exposés 1043–1058, Soc. Math. France, Paris, 2013, vol. 352, p. exp. no. 1047, viii, 147-159.
    @INCOLLECTION{Bal13,
      author = {Ball, Keith},
      title = {The {R}ibe programme},
      booktitle = {Séminaire Bourbaki. Vol. 2011/2012. Exposés 1043--1058},
      series = {Astérisque},
      publisher={Soc. Math. France, Paris},
      volume = {352},
      year = {2013},
      pages = {Exp. No. 1047, viii, 147--159},
      issn = {0303-1179},
      isbn = {978-2-85629-371-3},
      mrclass = {46B85 (46B07 60G46)},
      mrnumber = {3087345},
      mrreviewer = {Jesús A. Jaramillo},
      zblnumber = {1303.46019},
      }
  • [Bas72] Go to document H. Bass, "The degree of polynomial growth of finitely generated nilpotent groups," Proc. London Math. Soc. (3), vol. 25, pp. 603-614, 1972.
    @ARTICLE{Bas72,
      author = {Bass, H.},
      title = {The degree of polynomial growth of finitely generated nilpotent groups},
      journal = {Proc. London Math. Soc. (3)},
      fjournal = {Proceedings of the London Mathematical Society. Third Series},
      volume = {25},
      year = {1972},
      pages = {603--614},
      issn = {0024-6115},
      mrclass = {20F05},
      mrnumber = {0379672},
      mrreviewer = {I. B. S. Passi},
      doi = {10.1112/plms/s3-25.4.603},
      zblnumber = {0259.20045},
      }
  • [BBI01] Go to document D. Burago, Y. Burago, and S. Ivanov, A Course in Metric Geometry, Amer. Math. Soc., Providence, RI, 2001, vol. 33.
    @BOOK{BBI01,
      author = {Burago, Dmitri and Burago, Yuri and Ivanov, Sergei},
      title = {A Course in Metric Geometry},
      series = {Grad. Studies in Math.},
      volume = {33},
      publisher = {Amer. Math. Soc., Providence, RI},
      year = {2001},
      pages = {xiv+415},
      isbn = {0-8218-2129-6},
      mrclass = {53C23},
      mrnumber = {1835418},
      mrreviewer = {Mario Bonk},
      doi = {10.1090/gsm/033},
      zblnumber = {0981.51016},
      }
  • [BL00] Y. Benyamini and J. Lindenstrauss, Geometric Nonlinear Functional Analysis. Vol. 1, Amer. Math. Soc., Providence, RI, 2000, vol. 48.
    @BOOK{BL00,
      author = {Benyamini, Yoav and Lindenstrauss, Joram},
      title = {Geometric Nonlinear Functional Analysis. {V}ol. 1},
      series = {Amer. Math. Soc. Colloq. Publ.},
      volume = {48},
      publisher = {Amer. Math. Soc., Providence, RI},
      year = {2000},
      pages = {xii+488},
      isbn = {0-8218-0835-4},
      mrclass = {46-02 (46Bxx 46T99 47-02)},
      mrnumber = {1727673},
      mrreviewer = {Gilles Godefroy},
      zblnumber = {0946.46002},
      }
  • [BL08] Go to document F. Baudier and G. Lancien, "Embeddings of locally finite metric spaces into Banach spaces," Proc. Amer. Math. Soc., vol. 136, iss. 3, pp. 1029-1033, 2008.
    @ARTICLE{BL08,
      author = {Baudier, F. and Lancien, G.},
      title = {Embeddings of locally finite metric spaces into {B}anach spaces},
      journal = {Proc. Amer. Math. Soc.},
      fjournal = {Proceedings of the Amer. Math. Soc.},
      volume = {136},
      year = {2008},
      number = {3},
      pages = {1029--1033},
      issn = {0002-9939},
      mrclass = {46B20 (46B07)},
      mrnumber = {2361878},
      mrreviewer = {Piotr W. Nowak},
      doi = {10.1090/S0002-9939-07-09109-5},
      zblnumber = {1142.46037},
      }
  • [Bla03] Go to document S. Blachère, "Word distance on the discrete Heisenberg group," Colloq. Math., vol. 95, iss. 1, pp. 21-36, 2003.
    @ARTICLE{Bla03,
      author = {Blachère, Sébastien},
      title = {Word distance on the discrete {H}eisenberg group},
      journal = {Colloq. Math.},
      fjournal = {Colloquium Mathematicum},
      volume = {95},
      year = {2003},
      number = {1},
      pages = {21--36},
      issn = {0010-1354},
      mrclass = {20F65},
      mrnumber = {1967551},
      mrreviewer = {Piotr Haj\l asz},
      doi = {10.4064/cm95-1-2},
      zblnumber = {1010.05034},
      }
  • [Bou85] Go to document J. Bourgain, "On Lipschitz embedding of finite metric spaces in Hilbert space," Israel J. Math., vol. 52, iss. 1-2, pp. 46-52, 1985.
    @ARTICLE{Bou85,
      author = {Bourgain, J.},
      title = {On {L}ipschitz embedding of finite metric spaces in {H}ilbert space},
      journal = {Israel J. Math.},
      fjournal = {Israel Journal of Mathematics},
      volume = {52},
      year = {1985},
      number = {1-2},
      pages = {46--52},
      issn = {0021-2172},
      mrclass = {46B99 (05C80 58B05)},
      mrnumber = {0815600},
      mrreviewer = {Michel Deza},
      doi = {10.1007/BF02776078},
      zblnumber = {0657.46013},
      }
  • [Bou02] Go to document J. Bourgain, "On the distributions of the Fourier spectrum of Boolean functions," Israel J. Math., vol. 131, pp. 269-276, 2002.
    @ARTICLE{Bou02,
      author = {Bourgain, J.},
      title = {On the distributions of the {F}ourier spectrum of {B}oolean functions},
      journal = {Israel J. Math.},
      fjournal = {Israel Journal of Mathematics},
      volume = {131},
      year = {2002},
      pages = {269--276},
      issn = {0021-2172},
      mrclass = {43A75 (42A38)},
      mrnumber = {1942312},
      mrreviewer = {Colin C. Graham},
      doi = {10.1007/BF02785861},
      zblnumber = {1021.43004},
      }
  • [BS72] A. Brunel and L. Sucheston, "Sur quelques conditions équivalentes à la super-réflexivité dans les espaces de Banach," C. R. Acad. Sci. Paris Sér. A-B, vol. 275, p. a993-a994, 1972.
    @ARTICLE{BS72,
      author = {Brunel, Antoine and Sucheston, Louis},
      title = {Sur quelques conditions équivalentes à la super-réflexivité dans les espaces de {B}anach},
      journal = {C. R. Acad. Sci. Paris Sér. A-B},
      volume = {275},
      year = {1972},
      pages = {A993--A994},
      mrclass = {46B10},
      mrnumber = {0318843},
      mrreviewer = {J. T. Marti},
      zblnumber = {0245.46016},
      }
  • [CGR08] Go to document S. Chawla, A. Gupta, and H. Räcke, "Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut," ACM Trans. Algorithms, vol. 4, iss. 2, p. 22, 2008.
    @ARTICLE{CGR08,
      author = {Chawla, Shuchi and Gupta, Anupam and Räcke, Harald},
      title = {Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut},
      journal = {ACM Trans. Algorithms},
      fjournal = {ACM Transactions on Algorithms},
      volume = {4},
      year = {2008},
      number = {2},
      pages = {Art. 22, 18},
      issn = {1549-6325},
      mrclass = {68R10 (54E35)},
      mrnumber = {2419119},
      doi = {10.1145/1361192.1361199},
      zblnumber = {1297.68234},
      }
  • [Chawla08] Go to document S. Chawla, "Sparsest cut," in Encyclopedia of Algorithms, Springer-Verlag, New York, 2008, pp. 868-870.
    @INCOLLECTION{Chawla08,
      author = {Chawla, Shuchi},
      title = {Sparsest cut},
      booktitle = {Encyclopedia of Algorithms},
      pages = {868--870},
      publisher = {Springer-Verlag, New York},
      year = {2008},
      zblnumber = {},
      doi = {10.1007/978-0-387-30162-4_388},
      }
  • [ChristTb] Go to document M. Christ, "A $T(b)$ theorem with remarks on analytic capacity and the Cauchy integral," Colloq. Math., vol. 60/61, iss. 2, pp. 601-628, 1990.
    @ARTICLE{ChristTb,
      author = {Christ, Michael},
      title = {A {$T(b)$} theorem with remarks on analytic capacity and the {C}auchy integral},
      journal = {Colloq. Math.},
      fjournal = {Colloquium Mathematicum},
      volume = {60/61},
      year = {1990},
      number = {2},
      pages = {601--628},
      issn = {0010-1354},
      mrclass = {42B20 (42B25 42B30)},
      mrnumber = {1096400},
      mrreviewer = {Michael J. Wilson},
      doi = {10.4064/cm-60-61-2-601-628},
      zblnumber = {0758.42009},
      }
  • [CK06] Go to document J. Cheeger and B. Kleiner, "On the differentiability of Lipschitz maps from metric measure spaces to Banach spaces," in Inspired by S. S. Chern, World Sci. Publ., Hackensack, NJ, 2006, vol. 11, pp. 129-152.
    @INCOLLECTION{CK06,
      author = {Cheeger, Jeff and Kleiner, Bruce},
      title = {On the differentiability of {L}ipschitz maps from metric measure spaces to {B}anach spaces},
      booktitle = {Inspired by {S}. {S}. {C}hern},
      series = {Nankai Tracts Math.},
      volume = {11},
      pages = {129--152},
      publisher = {World Sci. Publ., Hackensack, NJ},
      year = {2006},
      mrclass = {46G05 (46B10 58C20)},
      mrnumber = {2313333},
      mrreviewer = {Hervé Pajot},
      doi = {10.1142/9789812772688_0006},
      zblnumber = {1139.58004},
      }
  • [CK07-hardness] Go to document J. Chuzhoy and S. Khanna, "Polynomial flow-cut gaps and hardness of directed cut problems [extended abstract]," in STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM, New York, 2007, pp. 179-188.
    @INCOLLECTION{CK07-hardness,
      author = {Chuzhoy, Julia and Khanna, Sanjeev},
      title = {Polynomial flow-cut gaps and hardness of directed cut problems [extended abstract]},
      booktitle = {S{TOC}'07---{P}roceedings of the 39th {A}nnual {ACM} {S}ymposium on {T}heory of {C}omputing},
      pages = {179--188},
      publisher = {ACM, New York},
      year = {2007},
      mrclass = {68Q17 (05C40 90C57)},
      mrnumber = {2402441},
      doi = {10.1145/1250790.1250817},
      zblnumber = {1232.68063},
      }
  • [CK09-hardness] Go to document J. Chuzhoy and S. Khanna, "Polynomial flow-cut gaps and hardness of directed cut problems," J. ACM, vol. 56, iss. 2, p. 6, 2009.
    @ARTICLE{CK09-hardness,
      author = {Chuzhoy, Julia and Khanna, Sanjeev},
      title = {Polynomial flow-cut gaps and hardness of directed cut problems},
      journal = {J. ACM},
      fjournal = {Journal of the ACM},
      volume = {56},
      year = {2009},
      number = {2},
      pages = {Art. 6, 28},
      issn = {0004-5411},
      mrclass = {68Q17 (05C20 05C85 68R10 90C35)},
      mrnumber = {2535879},
      mrreviewer = {Dimitrios M. Thilikos},
      doi = {10.1145/1502793.1502795},
      zblnumber = {1325.68096},
      }
  • [CK10] Go to document J. Cheeger and B. Kleiner, "Differentiating maps into $L^1$, and the geometry of BV functions," Ann. of Math. (2), vol. 171, iss. 2, pp. 1347-1385, 2010.
    @ARTICLE{CK10,
      author = {Cheeger, Jeff and Kleiner, Bruce},
      title = {Differentiating maps into {$L^1$},
      and the geometry of {BV} functions},
      journal = {Ann. of Math. (2)},
      fjournal = {Annals of Mathematics. Second Series},
      volume = {171},
      year = {2010},
      number = {2},
      pages = {1347--1385},
      issn = {0003-486X},
      mrclass = {30L05 (26A45 28A15 42B35 46B99 49Q15 53C23 68W25 90C22)},
      mrnumber = {2630066},
      mrreviewer = {Jeremy T. Tyson},
      doi = {10.4007/annals.2010.171.1347},
      zblnumber = {1194.22009},
      }
  • [CheegerKleinerMetricDiff] Go to document J. Cheeger and B. Kleiner, "Metric differentiation, monotonicity and maps to $L^1$," Invent. Math., vol. 182, iss. 2, pp. 335-370, 2010.
    @ARTICLE{CheegerKleinerMetricDiff,
      author = {Cheeger, Jeff and Kleiner, Bruce},
      title = {Metric differentiation, monotonicity and maps to {$L^1$}},
      journal = {Invent. Math.},
      fjournal = {Inventiones Mathematicae},
      volume = {182},
      year = {2010},
      number = {2},
      pages = {335--370},
      issn = {0020-9910},
      mrclass = {30L05 (28A15 46B85 58C20)},
      mrnumber = {2729270},
      mrreviewer = {Leonid V. Kovalev},
      doi = {10.1007/s00222-010-0264-9},
      zblnumber = {1214.46013},
      }
  • [CKKRS06] Go to document S. Chawla, R. Krauthgamer, R. Kumar, Y. Rabani, and D. Sivakumar, "On the hardness of approximating multicut and sparsest-cut," Comput. Complexity, vol. 15, iss. 2, pp. 94-114, 2006.
    @ARTICLE{CKKRS06,
      author = {Chawla, Shuchi and Krauthgamer, Robert and Kumar, Ravi and Rabani, Yuval and Sivakumar, D.},
      title = {On the hardness of approximating multicut and sparsest-cut},
      journal = {Comput. Complexity},
      fjournal = {Computational Complexity},
      volume = {15},
      year = {2006},
      number = {2},
      pages = {94--114},
      issn = {1016-3328},
      mrclass = {68Q17 (90C60)},
      mrnumber = {2243123},
      doi = {10.1007/s00037-006-0210-9},
      zblnumber = {1132.68418},
      }
  • [CKN09] Go to document J. Cheeger, B. Kleiner, and A. Naor, "A $(\log n)^{\Omega(1)}$ integrality gap for the sparsest cut SDP," in 2009 50th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2009, IEEE Computer Soc., Los Alamitos, CA, 2009, pp. 555-564.
    @INCOLLECTION{CKN09,
      author = {Cheeger, Jeff and Kleiner, Bruce and Naor, Assaf},
      title = {A {$(\log n)^{\Omega(1)}$} integrality gap for the sparsest cut {SDP}},
      booktitle = {2009 50th {A}nnual {IEEE} {S}ymposium on {F}oundations of {C}omputer {S}cience---{FOCS} 2009},
      pages = {555--564},
      publisher = {IEEE Computer Soc., Los Alamitos, CA},
      year = {2009},
      mrclass = {90C22 (90C57)},
      mrnumber = {2648435},
      doi = {10.1109/FOCS.2009.47},
      zblnumber = {1291.90318},
      }
  • [CKN] Go to document J. Cheeger, B. Kleiner, and A. Naor, "Compression bounds for Lipschitz maps from the Heisenberg group to $L_1$," Acta Math., vol. 207, iss. 2, pp. 291-373, 2011.
    @ARTICLE{CKN,
      author = {Cheeger, Jeff and Kleiner, Bruce and Naor, Assaf},
      title = {Compression bounds for {L}ipschitz maps from the {H}eisenberg group to {$L_1$}},
      journal = {Acta Math.},
      fjournal = {Acta Mathematica},
      volume = {207},
      year = {2011},
      number = {2},
      pages = {291--373},
      issn = {0001-5962},
      mrclass = {30L05 (28A15 46B85 58C20)},
      mrnumber = {2892612},
      mrreviewer = {Leonid V. Kovalev},
      doi = {10.1007/s11511-012-0071-9},
      zblnumber = {1247.46020},
      }
  • [Dav84] Go to document G. David, "Opérateurs intégraux singuliers sur certaines courbes du plan complexe," Ann. Sci. École Norm. Sup. (4), vol. 17, iss. 1, pp. 157-189, 1984.
    @ARTICLE{Dav84,
      author = {David, Guy},
      title = {Opérateurs intégraux singuliers sur certaines courbes du plan complexe},
      journal = {Ann. Sci. École Norm. Sup. (4)},
      fjournal = {Annales Scientifiques de l'École Normale Supérieure. Quatrième Série},
      volume = {17},
      year = {1984},
      number = {1},
      pages = {157--189},
      issn = {0012-9593},
      mrclass = {42A50 (30E20)},
      mrnumber = {0744071},
      mrreviewer = {Akihiko Miyachi},
      doi = {10.24033/asens.1469},
      zblnumber = {0537.42016},
      }
  • [DavidWavelets] Go to document G. David, Wavelets and Singular Integrals on Curves and Surfaces, Springer-Verlag, Berlin, 1991, vol. 1465.
    @BOOK{DavidWavelets,
      author = {David, Guy},
      title = {Wavelets and Singular Integrals on Curves and Surfaces},
      series = {Lecture Notes in Math.},
      volume = {1465},
      publisher = {Springer-Verlag, Berlin},
      year = {1991},
      pages = {x+107},
      isbn = {3-540-53902-6},
      mrclass = {42B20 (47G10)},
      mrnumber = {1123480},
      mrreviewer = {Stephen Buckley},
      doi = {10.1007/BFb0091544},
      zblnumber = {0764.42019},
      }
  • [DKSV06] Go to document N. R. Devanur, S. A. Khot, R. Saket, and N. K. Vishnoi, "Integrality gaps for sparsest cut and minimum linear arrangement problems," in STOC’06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, ACM, New York, 2006, pp. 537-546.
    @INCOLLECTION{DKSV06,
      author = {Devanur, Nikhil R. and Khot, Subhash A. and Saket, Rishi and Vishnoi, Nisheeth K.},
      title = {Integrality gaps for sparsest cut and minimum linear arrangement problems},
      booktitle = {S{TOC}'06: {P}roceedings of the 38th {A}nnual {ACM} {S}ymposium on {T}heory of {C}omputing},
      pages = {537--546},
      publisher = {ACM, New York},
      year = {2006},
      mrclass = {68Q25 (90B80)},
      mrnumber = {2277179},
      doi = {10.1145/1132516.1132594},
      zblnumber = {1301.05332},
      }
  • [DL97] Go to document M. M. Deza and M. Laurent, Geometry of Cuts and Metrics, Springer-Verlag, Berlin, 1997, vol. 15.
    @BOOK{DL97,
      author = {Deza, Michel Marie and Laurent, Monique},
      title = {Geometry of Cuts and Metrics},
      series = {Algorithms Combin.},
      volume = {15},
      publisher = {Springer-Verlag, Berlin},
      year = {1997},
      pages = {xii+587},
      isbn = {3-540-61611-X},
      mrclass = {52-02 (05B30 05C12 51K05 52B12 52C07 68R05 90C28)},
      mrnumber = {1460488},
      mrreviewer = {Alexander I. Barvinok},
      doi = {10.1007/978-3-642-04295-9},
      zblnumber = {0885.52001},
      }
  • [DLP13] Go to document J. Ding, J. R. Lee, and Y. Peres, "Markov type and threshold embeddings," Geom. Funct. Anal., vol. 23, iss. 4, pp. 1207-1229, 2013.
    @ARTICLE{DLP13,
      author = {Ding, Jian and Lee, James R. and Peres, Yuval},
      title = {Markov type and threshold embeddings},
      journal = {Geom. Funct. Anal.},
      fjournal = {Geometric and Functional Analysis},
      volume = {23},
      year = {2013},
      number = {4},
      pages = {1207--1229},
      issn = {1016-443X},
      mrclass = {46B85 (46B09 54E35 60B11 60G42 60J05)},
      mrnumber = {3077911},
      mrreviewer = {Yasunao Hattori},
      doi = {10.1007/s00039-013-0234-7},
      zblnumber = {1279.46013},
      }
  • [DavidSemmesSingular] G. David and S. Semmes, Singular integrals and rectifiable sets in ${\bf R}^n$: Beyond Lipschitz graphs, Soc. Math. France, Paris, 1991, vol. 193.
    @BOOK{DavidSemmesSingular,
      author = {David, G. and Semmes, S.},
      title = {Singular integrals and rectifiable sets in {${\bf R}^n$}: {B}eyond {L}ipschitz graphs},
      series = {Astérisque},
      fjournal = {Astérisque},
      publisher={Soc. Math. France, Paris},
      volume = {193},
      year = {1991},
      pages = {152 pp.},
      issn = {0303-1179},
      mrclass = {42B20 (42B25)},
      mrnumber = {1113517},
      mrreviewer = {Stephen Buckley},
      zblnumber = {0743.49018},
      }
  • [DSAnalysis] Go to document G. David and S. Semmes, Analysis of and on Uniformly Rectifiable Sets, Amer. Math. Soc., Providence, RI, 1993, vol. 38.
    @BOOK{DSAnalysis,
      author = {David, Guy and Semmes, Stephen},
      title = {Analysis of and on Uniformly Rectifiable Sets},
      series = {Math. Surveys Monogr.},
      volume = {38},
      publisher = {Amer. Math. Soc., Providence, RI},
      year = {1993},
      pages = {xii+356},
      isbn = {0-8218-1537-7},
      mrclass = {28A75 (30C65 30E20 42B20 42B25)},
      mrnumber = {1251061},
      mrreviewer = {Christopher Bishop},
      doi = {10.1090/surv/038},
      zblnumber = {0832.42008},
      }
  • [FSSCSerrinMeyer] Go to document B. Franchi, R. Serapioni, and F. Serra Cassano, "Meyers-Serrin type theorems and relaxation of variational integrals depending on vector fields," Houston J. Math., vol. 22, iss. 4, pp. 859-890, 1996.
    @ARTICLE{FSSCSerrinMeyer,
      author = {Franchi, Bruno and Serapioni, Raul and Serra Cassano, Francesco},
      title = {Meyers-{S}errin type theorems and relaxation of variational integrals depending on vector fields},
      journal = {Houston J. Math.},
      fjournal = {Houston Journal of Mathematics},
      volume = {22},
      year = {1996},
      number = {4},
      pages = {859--890},
      issn = {0362-1588},
      mrclass = {49J45 (35F20)},
      mrnumber = {1437714},
      mrreviewer = {Francesco Ferro},
      zblnumber = {0876.49014},
      url = {https://www.math.uh.edu/~hjm/restricted/archive/v022n4/0859FRANCHI.pdf},
      }
  • [FSSCRectifiability] Go to document B. Franchi, R. Serapioni, and F. Serra Cassano, "Rectifiability and perimeter in the Heisenberg group," Math. Ann., vol. 321, iss. 3, pp. 479-531, 2001.
    @ARTICLE{FSSCRectifiability,
      author = {Franchi, Bruno and Serapioni, Raul and Serra Cassano, Francesco},
      title = {Rectifiability and perimeter in the {H}eisenberg group},
      journal = {Math. Ann.},
      fjournal = {Mathematische Annalen},
      volume = {321},
      year = {2001},
      number = {3},
      pages = {479--531},
      issn = {0025-5831},
      mrclass = {49Q15 (22E25 46E35)},
      mrnumber = {1871966},
      mrreviewer = {Piotr Haj\l asz},
      doi = {10.1007/s002080100228},
      zblnumber = {1057.49032},
      }
  • [FSSC03] Go to document B. Franchi, R. Serapioni, and F. Serra Cassano, "On the structure of finite perimeter sets in step 2 Carnot groups," J. Geom. Anal., vol. 13, iss. 3, pp. 421-466, 2003.
    @ARTICLE{FSSC03,
      author = {Franchi, Bruno and Serapioni, Raul and Serra Cassano, Francesco},
      title = {On the structure of finite perimeter sets in step 2 {C}arnot groups},
      journal = {J. Geom. Anal.},
      fjournal = {The Journal of Geometric Analysis},
      volume = {13},
      year = {2003},
      number = {3},
      pages = {421--466},
      issn = {1050-6926},
      mrclass = {49Q15 (53C17)},
      mrnumber = {1984849},
      mrreviewer = {J. E. Brothers},
      doi = {10.1007/BF02922053},
      zblnumber = {1064.49033},
      }
  • [FSSC06] B. Franchi, R. Serapioni, and F. Serra Cassano, "Intrinsic Lipschitz graphs in Heisenberg groups," J. Nonlinear Convex Anal., vol. 7, iss. 3, pp. 423-441, 2006.
    @ARTICLE{FSSC06,
      author = {Franchi, Bruno and Serapioni, Raul and Serra Cassano, Francesco},
      title = {Intrinsic {L}ipschitz graphs in {H}eisenberg groups},
      journal = {J. Nonlinear Convex Anal.},
      fjournal = {Journal of Nonlinear and Convex Analysis. An International Journal},
      volume = {7},
      year = {2006},
      number = {3},
      pages = {423--441},
      issn = {1345-4773},
      mrclass = {58C20 (22E30)},
      mrnumber = {2287539},
      mrreviewer = {Thierry Coulhon},
      zblnumber = {1151.58005},
      }
  • [FSSCDifferentiability] Go to document B. Franchi, R. Serapioni, and F. Serra Cassano, "Differentiability of intrinsic Lipschitz functions within Heisenberg groups," J. Geom. Anal., vol. 21, iss. 4, pp. 1044-1084, 2011.
    @ARTICLE{FSSCDifferentiability,
      author = {Franchi, Bruno and Serapioni, Raul and Serra Cassano, Francesco},
      title = {Differentiability of intrinsic {L}ipschitz functions within {H}eisenberg groups},
      journal = {J. Geom. Anal.},
      fjournal = {Journal of Geometric Analysis},
      volume = {21},
      year = {2011},
      number = {4},
      pages = {1044--1084},
      issn = {1050-6926},
      mrclass = {22E30 (58C20)},
      mrnumber = {2836591},
      mrreviewer = {Davide Vittone},
      doi = {10.1007/s12220-010-9178-4},
      zblnumber = {1234.22002},
      }
  • [GKL03] Go to document A. Gupta, R. Krauthgamer, and J. R. Lee, "Bounded geometries, fractals, and low-distortion embeddings," in FOCS ’03 Proceedings of the 44th Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, 2003, pp. 534-543.
    @INCOLLECTION{GKL03,
      author = {Gupta, Anupam and Krauthgamer, Robert and Lee, James R.},
      title = {Bounded geometries, fractals, and low-distortion embeddings},
      booktitle = {FOCS '03 Proceedings of the 44th Symposium on Foundations of Computer Science},
      venue = {October 11--14, 2003, Cambridge, MA, USA},
      pages = {534--543},
      publisher = {{IEEE} Computer Society, Washington, DC},
      year = {2003},
      zblnumber = {},
      url = {https://dl.acm.org/citation.cfm?id=946308},
      }
  • [GLS93] Go to document M. Grötschel, L. Lovász, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Second ed., Springer-Verlag, Berlin, 1993, vol. 2.
    @BOOK{GLS93,
      author = {Grötschel, Martin and Lovász, László and Schrijver, Alexander},
      title = {Geometric Algorithms and Combinatorial Optimization},
      series = {Algorithms Combin.},
      volume = {2},
      edition = {Second},
      publisher = {Springer-Verlag, Berlin},
      year = {1993},
      pages = {xii+362},
      isbn = {3-540-56740-2},
      mrclass = {90-02 (52C07 90C27)},
      mrnumber = {1261419},
      mrreviewer = {Ulrich Faigle},
      doi = {10.1007/978-3-642-78240-4},
      zblnumber = {0837.05001},
      }
  • [GNIsoSob] Go to document N. Garofalo and D. Nhieu, "Isoperimetric and Sobolev inequalities for Carnot-Carathéodory spaces and the existence of minimal surfaces," Comm. Pure Appl. Math., vol. 49, iss. 10, pp. 1081-1144, 1996.
    @ARTICLE{GNIsoSob,
      author = {Garofalo, Nicola and Nhieu, Duy-Minh},
      title = {Isoperimetric and {S}obolev inequalities for {C}arnot-{C}arathéodory spaces and the existence of minimal surfaces},
      journal = {Comm. Pure Appl. Math.},
      fjournal = {Communications on Pure and Applied Mathematics},
      volume = {49},
      year = {1996},
      number = {10},
      pages = {1081--1144},
      issn = {0010-3640},
      mrclass = {58E12 (35H05 35J99 49Q05)},
      mrnumber = {1404326},
      mrreviewer = {Luca Capogna},
      doi = {10/dzvwvb},
      zblnumber = {0880.35032},
      }
  • [Goe97] Go to document M. X. Goemans, "Semidefinite programming in combinatorial optimization," Math. Programming, vol. 79, iss. 1-3, Ser. B, pp. 143-161, 1997.
    @ARTICLE{Goe97,
      author = {Goemans, Michel X.},
      title = {Semidefinite programming in combinatorial optimization},
      note = {Lectures on mathematical programming (ismp97) (Lausanne, 1997)},
      journal = {Math. Programming},
      fjournal = {Mathematical Programming},
      volume = {79},
      year = {1997},
      number = {1-3, Ser. B},
      pages = {143--161},
      issn = {0025-5610},
      mrclass = {90C27 (90-02)},
      mrnumber = {1464765},
      mrreviewer = {D. de Werra},
      doi = {10.1007/BF02614315},
      zblnumber = {0887.90139},
      }
  • [Gro81] Go to document M. Gromov, "Groups of polynomial growth and expanding maps," Inst. Hautes Études Sci. Publ. Math., vol. 53, pp. 53-73, 1981.
    @ARTICLE{Gro81,
      author = {Gromov, Mikhael},
      title = {Groups of polynomial growth and expanding maps},
      journal = {Inst. Hautes Études Sci. Publ. Math.},
      fjournal = {Institut des Hautes Études Scientifiques. Publications Mathématiques},
      volume = {53},
      year = {1981},
      pages = {53--73},
      issn = {0073-8301},
      mrclass = {53C20 (22E40 58F15)},
      mrnumber = {0623534},
      mrreviewer = {J. A. Wolf},
      doi = {10.1007/BF02698687},
      zblnumber = {0474.20018},
      }
  • [Gro96] M. Gromov, "Carnot-Carathéodory spaces seen from within," in Sub-Riemannian Geometry, Birkhäuser, Basel, 1996, vol. 144, pp. 79-323.
    @INCOLLECTION{Gro96,
      author = {Gromov, Mikhael},
      title = {Carnot-{C}arathéodory spaces seen from within},
      booktitle = {Sub-{R}iemannian Geometry},
      series = {Progr. Math.},
      volume = {144},
      pages = {79--323},
      publisher = {Birkhäuser, Basel},
      year = {1996},
      mrclass = {53C17 (53C23)},
      mrnumber = {1421823},
      mrreviewer = {Richard W. Montgomery},
      zblnumber = {0864.53025},
      }
  • [Hein80] Go to document S. Heinrich, "Ultraproducts in Banach space theory," J. Reine Angew. Math., vol. 313, pp. 72-104, 1980.
    @ARTICLE{Hein80,
      author = {Heinrich, Stefan},
      title = {Ultraproducts in {B}anach space theory},
      journal = {J. Reine Angew. Math.},
      fjournal = {Journal für die Reine und Angewandte Mathematik},
      volume = {313},
      year = {1980},
      pages = {72--104},
      issn = {0075-4102},
      mrclass = {46Bxx (03C20 03H20 46-02)},
      mrnumber = {0552464},
      mrreviewer = {C. Ward Henson},
      doi = {10.1515/crll.1980.313.72},
      zblnumber = {0412.46017},
      }
  • [HajKos] Go to document P. Hajłasz and P. Koskela, "Sobolev met Poincaré," Mem. Amer. Math. Soc., vol. 145, iss. 688, p. x, 2000.
    @ARTICLE{HajKos,
      author = {Haj{\l}asz, Piotr and Koskela, Pekka},
      title = {Sobolev met {P}oincaré},
      journal = {Mem. Amer. Math. Soc.},
      fjournal = {Memoirs of the Amer. Math. Soc.},
      volume = {145},
      year = {2000},
      number = {688},
      pages = {x+101},
      issn = {0065-9266},
      mrclass = {46E35 (30C65 31C25 53C17 58J60)},
      mrnumber = {1683160},
      mrreviewer = {Alexander D. Ukhlov},
      doi = {10.1090/memo/0688},
      zblnumber = {0954.46022},
      }
  • [JLM11] Go to document A. Jaffe, J. R. Lee, and M. Moharrami, "On the optimality of gluing over scales," Discrete Comput. Geom., vol. 46, iss. 2, pp. 270-282, 2011.
    @ARTICLE{JLM11,
      author = {Jaffe, Alexander and Lee, James R. and Moharrami, Mohammad},
      title = {On the optimality of gluing over scales},
      journal = {Discrete Comput. Geom.},
      fjournal = {Discrete \& Computational Geometry. An International Journal of Mathematics and Computer Science},
      volume = {46},
      year = {2011},
      number = {2},
      pages = {270--282},
      issn = {0179-5376},
      mrclass = {51F99 (54E35)},
      mrnumber = {2812509},
      doi = {10.1007/s00454-011-9359-3},
      zblnumber = {1219.68159},
      }
  • [Jon89] Go to document P. W. Jones, "Square functions, Cauchy integrals, analytic capacity, and harmonic measure," in Harmonic Analysis and Partial Differential Equations, Springer, Berlin, 1989, vol. 1384, pp. 24-68.
    @INCOLLECTION{Jon89,
      author = {Jones, Peter W.},
      title = {Square functions, {C}auchy integrals, analytic capacity, and harmonic measure},
      booktitle = {Harmonic Analysis and Partial Differential Equations},
      venue = {{E}l {E}scorial, 1987},
      series = {Lecture Notes in Math.},
      volume = {1384},
      pages = {24--68},
      publisher = {Springer, Berlin},
      year = {1989},
      mrclass = {42B20 (31A15 42B25 42B30)},
      mrnumber = {1013815},
      mrreviewer = {Matts Essén},
      doi = {10.1007/BFb0086793},
      zblnumber = {0675.30029},
      }
  • [Jon90] Go to document P. W. Jones, "Rectifiable sets and the traveling salesman problem," Invent. Math., vol. 102, iss. 1, pp. 1-15, 1990.
    @ARTICLE{Jon90,
      author = {Jones, Peter W.},
      title = {Rectifiable sets and the traveling salesman problem},
      journal = {Invent. Math.},
      fjournal = {Inventiones Mathematicae},
      volume = {102},
      year = {1990},
      number = {1},
      pages = {1--15},
      issn = {0020-9910},
      mrclass = {26B15 (05C38 28A75 30E10 42C99 90C10)},
      mrnumber = {1069238},
      mrreviewer = {Pertti Mattila},
      doi = {10.1007/BF01233418},
      zblnumber = {0731.30018},
      }
  • [Kad58] Go to document M. I. Kadec, "Linear dimension of the spaces $L_{p}$ and $l_{q}$," Uspehi Mat. Nauk, vol. 13, iss. 6 (84), pp. 95-98, 1958.
    @ARTICLE{Kad58,
      author = {Kadec, M. I.},
      title = {Linear dimension of the spaces {$L\sb{p}$} and {$l\sb{q}$}},
      journal = {Uspehi Mat. Nauk},
      fjournal = {Akademiya Nauk SSSR i Moskovskoe Matematicheskoe Obshchestvo. Uspekhi Matematicheskikh Nauk},
      volume = {13},
      year = {1958},
      number = {6 (84)},
      pages = {95--98},
      issn = {0042-1316},
      mrclass = {46.00},
      mrnumber = {0101486},
      mrreviewer = {M. Jerison},
      zblnumber = {0087.10802},
      url = {http://mi.mathnet.ru/eng/umn/v13/i6/p95},
      }
  • [Kho02] Go to document 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, 2002, pp. 767-775.
    @INPROCEEDINGS{Kho02,
      author = {Khot, Subhash},
      title = {On the power of unique 2-prover 1-round games},
      booktitle = {Proceedings of the {T}hirty-{F}ourth {A}nnual {ACM} {S}ymposium on {T}heory of {C}omputing},
      pages = {767--775},
      publisher = {ACM, New York},
      year = {2002},
      mrclass = {68Q25 (68Q15)},
      mrnumber = {2121525},
      doi = {10.1145/509907.510017},
      zblnumber = {1192.68367},
      }
  • [Kho10] Go to document S. Khot, "Inapproximability of NP-complete problems, discrete Fourier analysis, and geometry," in Proceedings of the International Congress of Mathematicians 2010 (ICM 2010). Volume IV, 2012, pp. 2676-2697.
    @INPROCEEDINGS{Kho10,
      author = {Khot, Subhash},
      title = {Inapproximability of {NP}-complete problems, discrete {F}ourier analysis, and geometry},
      booktitle = {Proceedings of the {I}nternational {C}ongress of {M}athematicians 2010 (ICM 2010). {V}olume {IV}},
      pages = {2676--2697},
      publisher = {Hindustan Book Agency, New Delhi},
      year = {2012},
      mrclass = {68Q17},
      mrnumber = {2827989},
      zblnumber = {1252.68143},
      doi = {10.1142/9789814324359_0163},
      }
  • [Kir94] Go to document B. Kirchheim, "Rectifiable metric spaces: local structure and regularity of the Hausdorff measure," Proc. Amer. Math. Soc., vol. 121, iss. 1, pp. 113-123, 1994.
    @ARTICLE{Kir94,
      author = {Kirchheim, Bernd},
      title = {Rectifiable metric spaces: local structure and regularity of the {H}ausdorff measure},
      journal = {Proc. Amer. Math. Soc.},
      fjournal = {Proceedings of the Amer. Math. Soc.},
      volume = {121},
      year = {1994},
      number = {1},
      pages = {113--123},
      issn = {0002-9939},
      mrclass = {28A78},
      mrnumber = {1189747},
      mrreviewer = {G. Freilich},
      doi = {10.2307/2160371},
      zblnumber = {0806.28004},
      }
  • [KKL88] Go to document J. Kahn, G. Kalai, and N. Linial, "The influence of variables on Boolean functions (extended abstract)," in 29th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, 1988, pp. 68-80.
    @INCOLLECTION{KKL88,
      author = {Kahn, Jeff and Kalai, Gil and Linial, Nathan},
      title = {The influence of variables on {B}oolean functions (extended abstract)},
      booktitle = {29th Annual Symposium on Foundations of Computer Science},
      venue = {White Plains, New York, USA, 24-26 October 1988},
      pages = {68--80},
      publisher = {{IEEE} Computer Society},
      year = {1988},
      zblnumber = {},
      doi = {10.1109/SFCS.1988.21923},
      }
  • [Kle10] Go to document B. Kleiner, "A new proof of Gromov’s theorem on groups of polynomial growth," J. Amer. Math. Soc., vol. 23, iss. 3, pp. 815-829, 2010.
    @ARTICLE{Kle10,
      author = {Kleiner, Bruce},
      title = {A new proof of {G}romov's theorem on groups of polynomial growth},
      journal = {J. Amer. Math. Soc.},
      fjournal = {Journal of the Amer. Math. Soc.},
      volume = {23},
      year = {2010},
      number = {3},
      pages = {815--829},
      issn = {0894-0347},
      mrclass = {20F65 (20F67 20F69)},
      mrnumber = {2629989},
      mrreviewer = {François Dahmani},
      doi = {10.1090/S0894-0347-09-00658-4},
      zblnumber = {1246.20038},
      }
  • [KLMN05] Go to document R. Krauthgamer, J. R. Lee, M. Mendel, and A. Naor, "Measured descent: a new embedding method for finite metrics," Geom. Funct. Anal., vol. 15, iss. 4, pp. 839-858, 2005.
    @ARTICLE{KLMN05,
      author = {Krauthgamer, R. and Lee, J. R. and Mendel, M. and Naor, A.},
      title = {Measured descent: a new embedding method for finite metrics},
      journal = {Geom. Funct. Anal.},
      fjournal = {Geometric and Functional Analysis},
      volume = {15},
      year = {2005},
      number = {4},
      pages = {839--858},
      issn = {1016-443X},
      mrclass = {68W25 (46B20 46E30 54E35 68R10)},
      mrnumber = {2221152},
      mrreviewer = {Marcello Sanguineti},
      doi = {10.1007/s00039-005-0527-6},
      zblnumber = {1108.46010},
      }
  • [KM13] Go to document D. Kane and R. Meka, "A PRG for Lipschitz functions of polynomials with applications to sparsest cut," in STOC’13—Proceedings of the 2013 ACM Symposium on Theory of Computing, ACM, New York, 2013, pp. 1-10.
    @INCOLLECTION{KM13,
      author = {Kane, Daniel and Meka, Raghu},
      title = {A {PRG} for {L}ipschitz functions of polynomials with applications to sparsest cut},
      booktitle = {S{TOC}'13---{P}roceedings of the 2013 {ACM} {S}ymposium on {T}heory of {C}omputing},
      pages = {1--10},
      publisher = {ACM, New York},
      year = {2013},
      mrclass = {68Q87 (68Q17)},
      mrnumber = {3210761},
      doi = {10.1145/2488608.2488610},
      zblnumber = {1293.65007},
      }
  • [KN06] Go to document S. Khot and A. Naor, "Nonembeddability theorems via Fourier analysis," Math. Ann., vol. 334, iss. 4, pp. 821-852, 2006.
    @ARTICLE{KN06,
      author = {Khot, Subhash and Naor, Assaf},
      title = {Nonembeddability theorems via {F}ourier analysis},
      journal = {Math. Ann.},
      fjournal = {Mathematische Annalen},
      volume = {334},
      year = {2006},
      number = {4},
      pages = {821--852},
      issn = {0025-5831},
      mrclass = {46B20 (42B35 54E40 68W25)},
      mrnumber = {2209259},
      doi = {10.1007/s00208-005-0745-0},
      zblnumber = {1102.46051},
      }
  • [KR09] Go to document R. Krauthgamer and Y. Rabani, "Improved lower bounds for embeddings into $L_1$," SIAM J. Comput., vol. 38, iss. 6, pp. 2487-2498, 2009.
    @ARTICLE{KR09,
      author = {Krauthgamer, Robert and Rabani, Yuval},
      title = {Improved lower bounds for embeddings into {$L_1$}},
      journal = {SIAM J. Comput.},
      fjournal = {SIAM Journal on Computing},
      volume = {38},
      year = {2009},
      number = {6},
      pages = {2487--2498},
      issn = {0097-5397},
      mrclass = {68W25 (46B85 68R10 90B22 90C27)},
      mrnumber = {2506299},
      mrreviewer = {Xinhui Wang},
      doi = {10.1137/060660126},
      zblnumber = {1191.68869},
      }
  • [KV15] Go to document S. A. Khot and N. K. Vishnoi, "The unique games conjecture, integrability gap for cut problems and embeddability of negative-type metrics into $\ell_1$," J. ACM, vol. 62, iss. 1, p. 8, 2015.
    @ARTICLE{KV15,
      author = {Khot, Subhash A. and Vishnoi, Nisheeth K.},
      title = {The unique games conjecture, integrability gap for cut problems and embeddability of negative-type metrics into {$\ell_1$}},
      journal = {J. ACM},
      fjournal = {Journal of the ACM},
      volume = {62},
      year = {2015},
      number = {1},
      pages = {Art. 8, 39},
      issn = {0004-5411},
      mrclass = {68Q25 (05C85 68Q15 90C27)},
      mrnumber = {3323774},
      doi = {10.1145/2629614},
      zblnumber = {1321.68316},
      }
  • [Lee05] J. R. Lee, "On distance scales, embeddings, and efficient relaxations of the cut cone," in Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005, pp. 92-101.
    @INPROCEEDINGS{Lee05,
      author = {Lee, James R.},
      title = {On distance scales, embeddings, and efficient relaxations of the cut cone},
      booktitle = {Proceedings of the {S}ixteenth {A}nnual {ACM}-{SIAM} {S}ymposium on {D}iscrete {A}lgorithms},
      pages = {92--101},
      publisher = {ACM, New York},
      year = {2005},
      mrclass = {90C10 (05C10 54C40)},
      mrnumber = {2298254},
      zblnumber = {1297.68244},
      }
  • [Li14] Go to document S. Li, "Coarse differentiation and quantitative nonembeddability for Carnot groups," J. Funct. Anal., vol. 266, iss. 7, pp. 4616-4704, 2014.
    @ARTICLE{Li14,
      author = {Li, Sean},
      title = {Coarse differentiation and quantitative nonembeddability for {C}arnot groups},
      journal = {J. Funct. Anal.},
      fjournal = {Journal of Functional Analysis},
      volume = {266},
      year = {2014},
      number = {7},
      pages = {4616--4704},
      issn = {0022-1236},
      mrclass = {53C23 (22E25 30L05 46B85 58C20)},
      mrnumber = {3170215},
      mrreviewer = {Leonid V. Kovalev},
      doi = {10.1016/j.jfa.2014.01.026},
      zblnumber = {1311.46021},
      }
  • [Li16] Go to document S. Li, "Markov convexity and nonembeddability of the Heisenberg group," Ann. Inst. Fourier (Grenoble), vol. 66, iss. 4, pp. 1615-1651, 2016.
    @ARTICLE{Li16,
      author = {Li, Sean},
      title = {Markov convexity and nonembeddability of the {H}eisenberg group},
      journal = {Ann. Inst. Fourier (Grenoble)},
      fjournal = {Université de Grenoble. Annales de l'Institut Fourier},
      volume = {66},
      year = {2016},
      number = {4},
      pages = {1615--1651},
      issn = {0373-0956},
      mrclass = {30L05 (22E25 46B85 53C23)},
      mrnumber = {3494180},
      mrreviewer = {Mikhail Ostrovskii},
      doi = {10.5802/aif.3045},
      zblnumber = {06680283},
      }
  • [Lin02] N. Linial, "Finite metric-spaces—combinatorics, geometry and algorithms," in Proceedings of the International Congress of Mathematicians, Vol. III, 2002, pp. 573-586.
    @INPROCEEDINGS{Lin02,
      author = {Linial, Nathan},
      title = {Finite metric-spaces---combinatorics, geometry and algorithms},
      booktitle = {Proceedings of the {I}nternational {C}ongress of {M}athematicians, {V}ol. {III}},
      venue = {{B}eijing, 2002},
      pages = {573--586},
      publisher = {Higher Ed. Press, Beijing},
      year = {2002},
      mrclass = {05C12 (68W25)},
      mrnumber = {1957562},
      mrreviewer = {Martin Knor},
      zblnumber = {0997.05019},
      }
  • [Lin-open] Go to document N. Linial, "Squared $\ell_2$ metrics into $\ell_1$," in Open Problems on Embeddings of Finite Metric Spaces, , 2002, p. 5.
    @INCOLLECTION{Lin-open,
      author = {Linial, Nathan},
      title = {Squared $\ell_2$ metrics into $\ell_1$},
      booktitle = {Open Problems on Embeddings of Finite Metric Spaces},
      note = {edited by {J. M}atoušek},
      pages = {5},
      year = {2002},
      zblnumber = {},
      url = {http://students.mimuw.edu.pl/~mk249015/www10/metrop.pdf},
      }
  • [LLR95] Go to document N. Linial, E. London, and Y. Rabinovich, "The geometry of graphs and some of its algorithmic applications," Combinatorica, vol. 15, iss. 2, pp. 215-245, 1995.
    @ARTICLE{LLR95,
      author = {Linial, Nathan and London, Eran and Rabinovich, Yuri},
      title = {The geometry of graphs and some of its algorithmic applications},
      journal = {Combinatorica},
      fjournal = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
      volume = {15},
      year = {1995},
      number = {2},
      pages = {215--245},
      issn = {0209-9683},
      mrclass = {05C85 (52B55 68R10)},
      mrnumber = {1337355},
      doi = {10.1007/BF01200757},
      zblnumber = {0827.05021},
      }
  • [LMN05] Go to document J. R. Lee, M. Mendel, and A. Naor, "Metric structures in $L_1$: dimension, snowflakes, and average distortion," European J. Combin., vol. 26, iss. 8, pp. 1180-1190, 2005.
    @ARTICLE{LMN05,
      author = {Lee, James R. and Mendel, Manor and Naor, Assaf},
      title = {Metric structures in {$L_1$}: dimension, snowflakes, and average distortion},
      journal = {European J. Combin.},
      fjournal = {European Journal of Combinatorics},
      volume = {26},
      year = {2005},
      number = {8},
      pages = {1180--1190},
      issn = {0195-6698},
      mrclass = {46B07 (05C10 05C85 46E30 51K05 52A21 54C25 68W25)},
      mrnumber = {2163751},
      doi = {10.1016/j.ejc.2004.07.002},
      zblnumber = {1106.68086},
      }
  • [LN06] Go to document J. 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, IEEE Computer Soc., Los Alamitos, CA, 2006, pp. 99-108.
    @INCOLLECTION{LN06,
      author = {Lee, James~R. and Naor, Assaf},
      title = {${L}_p$ metrics on the {H}eisenberg group and the {G}oemans-{L}inial conjecture},
      booktitle = {Proceedings of 47th Annual IEEE Symposium on Foundations of Computer Science},
      publisher = {IEEE Computer Soc., Los Alamitos, CA},
      venue = {FOCS 2006},
      pages = {99--108},
      year = {2006},
      zblnumber = {},
      doi = {10.1109/FOCS.2006.47},
      }
  • [LN14] Go to document V. Lafforgue and A. Naor, "A doubling subset of $L_p$ for $p>2$ that is inherently infinite dimensional," Geom. Dedicata, vol. 172, pp. 387-398, 2014.
    @ARTICLE{LN14,
      author = {Lafforgue, Vincent and Naor, Assaf},
      title = {A doubling subset of {$L_p$} for {$p>2$} that is inherently infinite dimensional},
      journal = {Geom. Dedicata},
      fjournal = {Geometriae Dedicata},
      volume = {172},
      year = {2014},
      pages = {387--398},
      issn = {0046-5755},
      mrclass = {30L05 (20F65 46E30)},
      mrnumber = {3253787},
      mrreviewer = {Sergei Merenkov},
      doi = {10.1007/s10711-013-9924-4},
      zblnumber = {1305.30029},
      }
  • [LafforgueNaor] Go to document V. Lafforgue and A. Naor, "Vertical versus horizontal Poincaré inequalities on the Heisenberg group," Israel J. Math., vol. 203, iss. 1, pp. 309-339, 2014.
    @ARTICLE{LafforgueNaor,
      author = {Lafforgue, Vincent and Naor, Assaf},
      title = {Vertical versus horizontal {P}oincaré inequalities on the {H}eisenberg group},
      journal = {Israel J. Math.},
      fjournal = {Israel Journal of Mathematics},
      volume = {203},
      year = {2014},
      number = {1},
      pages = {309--339},
      issn = {0021-2172},
      mrclass = {43A07 (20F65)},
      mrnumber = {3273443},
      mrreviewer = {Stefan Schröer},
      doi = {10.1007/s11856-014-1088-x},
      zblnumber = {1312.46032},
      }
  • [LNP09] Go to document J. R. Lee, A. Naor, and Y. Peres, "Trees and Markov convexity," Geom. Funct. Anal., vol. 18, iss. 5, pp. 1609-1659, 2009.
    @ARTICLE{LNP09,
      author = {Lee, James R. and Naor, Assaf and Peres, Yuval},
      title = {Trees and {M}arkov convexity},
      journal = {Geom. Funct. Anal.},
      fjournal = {Geometric and Functional Analysis},
      volume = {18},
      year = {2009},
      number = {5},
      pages = {1609--1659},
      issn = {1016-443X},
      mrclass = {05C05 (05C12 51F99 60B99)},
      mrnumber = {2481738},
      doi = {10.1007/s00039-008-0689-0},
      zblnumber = {1171.05318},
      }
  • [LR99] Go to document T. Leighton and S. Rao, "Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms," J. ACM, vol. 46, iss. 6, pp. 787-832, 1999.
    @ARTICLE{LR99,
      author = {Leighton, Tom and Rao, Satish},
      title = {Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms},
      journal = {J. ACM},
      fjournal = {Journal of the ACM},
      volume = {46},
      year = {1999},
      number = {6},
      pages = {787--832},
      issn = {0004-5411},
      mrclass = {05C85 (68Q25 68R10 68W25 68W40 90B10)},
      mrnumber = {1753034},
      mrreviewer = {Marek Kubale},
      doi = {10.1145/331524.331526},
      zblnumber = {1065.68666},
      }
  • [LS11] Go to document J. R. Lee and A. Sidiropoulos, "Near-optimal distortion bounds for embedding doubling spaces into $L_1$ [extended abstract]," in STOC’11—Proceedings of the 43rd ACM Symposium on Theory of Computing, ACM, New York, 2011, pp. 765-772.
    @INCOLLECTION{LS11,
      author = {Lee, James R. and Sidiropoulos, Anastasios},
      title = {Near-optimal distortion bounds for embedding doubling spaces into {$L_1$} [extended abstract]},
      booktitle = {S{TOC}'11---{P}roceedings of the 43rd {ACM} {S}ymposium on {T}heory of {C}omputing},
      pages = {765--772},
      publisher = {ACM, New York},
      year = {2011},
      mrclass = {90C27 (68W25)},
      mrnumber = {2932027},
      doi = {10.1145/1993636.1993737},
      zblnumber = {1288.90079},
      }
  • [Mat02] Go to document J. Matouvsek, Lectures on Discrete Geometry, Springer-Verlag, New York, 2002, vol. 212.
    @BOOK{Mat02,
      author = {Matou{š}ek, Ji{\v{r}}{\'ı}},
      title = {Lectures on Discrete Geometry},
      series = {Grad. Texts in Math.},
      volume = {212},
      publisher = {Springer-Verlag, New York},
      year = {2002},
      pages = {xvi+481},
      isbn = {0-387-95373-6},
      mrclass = {52Cxx (52-01)},
      mrnumber = {1899299},
      mrreviewer = {E. Hertel},
      doi = {10.1007/978-1-4613-0039-7},
      zblnumber = {0999.52006},
      }
  • [Mau03] Go to document B. Maurey, "Type, cotype and $K$-convexity," in Handbook of the Geometry of Banach Sspaces, Vol. 2, North-Holland, Amsterdam, 2003, pp. 1299-1332.
    @INCOLLECTION{Mau03,
      author = {Maurey, Bernard},
      title = {Type, cotype and {$K$}-convexity},
      booktitle = {Handbook of the Geometry of {B}anach Sspaces, {V}ol. 2},
      pages = {1299--1332},
      publisher = {North-Holland, Amsterdam},
      year = {2003},
      mrclass = {46B03 (46B07 46B08 46B20)},
      mrnumber = {1999197},
      mrreviewer = {Françoise Lust-Piquard},
      doi = {10.1016/S1874-5849(03)80037-2},
      zblnumber = {1074.46006},
      }
  • [McS34] Go to document E. J. McShane, "Extension of range of functions," Bull. Amer. Math. Soc., vol. 40, iss. 12, pp. 837-842, 1934.
    @ARTICLE{McS34,
      author = {McShane, E. J.},
      title = {Extension of range of functions},
      journal = {Bull. Amer. Math. Soc.},
      fjournal = {Bulletin of the Amer. Math. Soc.},
      volume = {40},
      year = {1934},
      number = {12},
      pages = {837--842},
      issn = {0002-9904},
      mrclass = {DML},
      mrnumber = {1562984},
      doi = {10.1090/S0002-9904-1934-05978-0},
      zblnumber = {60.0973.02},
      }
  • [Men09] M. Mendel, "Metric dichotomies," in Limits of Graphs in Group Theory and Computer Science, EPFL Press, Lausanne, 2009, pp. 59-76.
    @INCOLLECTION{Men09,
      author = {Mendel, Manor},
      title = {Metric dichotomies},
      booktitle = {Limits of Graphs in Group Theory and Computer Science},
      pages = {59--76},
      publisher = {EPFL Press, Lausanne},
      year = {2009},
      mrclass = {46B85 (54E35)},
      mrnumber = {2562140},
      mrreviewer = {Jeremy T. Tyson},
      zblnumber = {1293.05386},
      }
  • [MMV14] Go to document K. Makarychev, Y. Makarychev, and A. Vijayaraghavan, "Bilu-Linial stable instances of max cut and minimum multiway cut," in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014, pp. 890-906.
    @INPROCEEDINGS{MMV14,
      author = {Makarychev, Konstantin and Makarychev, Yury and Vijayaraghavan, Aravindan},
      title = {Bilu-{L}inial stable instances of max cut and minimum multiway cut},
      booktitle = {Proceedings of the {T}wenty-{F}ifth {A}nnual {ACM}-{SIAM} {S}ymposium on {D}iscrete {A}lgorithms},
      pages = {890--906},
      publisher = {ACM, New York},
      year = {2014},
      mrclass = {68Q25},
      mrnumber = {3376427},
      doi = {10.1137/1.9781611973402.67},
      zblnumber = {1315.05114},
      }
  • [MN11-arxiv] M. Mendel and A. Naor, A note on dichotomies for metric transforms, 2011.
    @MISC{MN11-arxiv,
      author = {Mendel, Manor and Naor, Assaf},
      title = {A note on dichotomies for metric transforms},
      arxiv = {1102.1800},
      year = {2011},
      }
  • [MN13] Go to document M. Mendel and A. Naor, "Markov convexity and local rigidity of distorted metrics," J. Eur. Math. Soc. (JEMS), vol. 15, iss. 1, pp. 287-337, 2013.
    @ARTICLE{MN13,
      author = {Mendel, Manor and Naor, Assaf},
      title = {Markov convexity and local rigidity of distorted metrics},
      journal = {J. Eur. Math. Soc. (JEMS)},
      fjournal = {Journal of the European Mathematical Society (JEMS)},
      volume = {15},
      year = {2013},
      number = {1},
      pages = {287--337},
      issn = {1435-9855},
      mrclass = {46B03 (46B85)},
      mrnumber = {2998836},
      mrreviewer = {Enrique Llorens Fuster},
      doi = {10.4171/JEMS/362},
      zblnumber = {1266.46016},
      }
  • [Mon02] R. Montgomery, A Tour of Subriemannian Geometries, Their Geodesics and Applications, Amer. Math. Soc., Providence, RI, 2002, vol. 91.
    @BOOK{Mon02,
      author = {Montgomery, Richard},
      title = {A {T}our of {S}ubriemannian {G}eometries, {T}heir {G}eodesics and {A}pplications},
      series = {Math. Surveys Monogr.},
      volume = {91},
      publisher = {Amer. Math. Soc., Providence, RI},
      year = {2002},
      pages = {xx+259},
      isbn = {0-8218-1391-9},
      mrclass = {53C17 (37J99 53C60 58E10 70G45 70H05)},
      mrnumber = {1867362},
      mrreviewer = {Andrey V. Sarychev},
      zblnumber = {1044.53022},
      }
  • [Mon05] Go to document F. Montefalcone, "Some relations among volume, intrinsic perimeter and one-dimensional restrictions of BV functions in Carnot groups," Ann. Sc. Norm. Super. Pisa Cl. Sci. (5), vol. 4, iss. 1, pp. 79-128, 2005.
    @ARTICLE{Mon05,
      author = {Montefalcone, Francescopaolo},
      title = {Some relations among volume, intrinsic perimeter and one-dimensional restrictions of {BV} functions in {C}arnot groups},
      journal = {Ann. Sc. Norm. Super. Pisa Cl. Sci. (5)},
      fjournal = {Annali della Scuola Normale Superiore di Pisa. Classe di Scienze. Serie V},
      volume = {4},
      year = {2005},
      number = {1},
      pages = {79--128},
      issn = {0391-173X},
      mrclass = {49Q20 (46E35 49Q15 53C17)},
      mrnumber = {2165404},
      mrreviewer = {H. R. Gluck},
      zblnumber = {1150.49022},
      doi = {10.2422/2036-2145.2005.1.04},
      }
  • [MP76] Go to document B. Maurey and G. Pisier, "Séries de variables aléatoires vectorielles indépendantes et propriétés géométriques des espaces de Banach," Studia Math., vol. 58, iss. 1, pp. 45-90, 1976.
    @ARTICLE{MP76,
      author = {Maurey, Bernard and Pisier, Gilles},
      title = {Séries de variables aléatoires vectorielles indépendantes et propriétés géométriques des espaces de {B}anach},
      journal = {Studia Math.},
      fjournal = {Polska Akademia Nauk. Instytut Matematyczny. Studia Mathematica},
      volume = {58},
      year = {1976},
      number = {1},
      pages = {45--90},
      issn = {0039-3223},
      mrclass = {60B05 (46B05)},
      mrnumber = {0443015},
      mrreviewer = {J. Hoffmann-Jorgensen},
      doi = {10.4064/sm-58-1-45-90},
      zblnumber = {0344.47014},
      }
  • [MTX06] Go to document T. Mart’inez, J. L. Torrea, and Q. Xu, "Vector-valued Littlewood-Paley-Stein theory for semigroups," Adv. Math., vol. 203, iss. 2, pp. 430-475, 2006.
    @ARTICLE{MTX06,
      author = {Mart{\'ı}nez, Teresa and Torrea, José L. and Xu, Quanhua},
      title = {Vector-valued {L}ittlewood-{P}aley-{S}tein theory for semigroups},
      journal = {Adv. Math.},
      fjournal = {Advances in Mathematics},
      volume = {203},
      year = {2006},
      number = {2},
      pages = {430--475},
      issn = {0001-8708},
      mrclass = {47D06 (42B25 46B20 47D07)},
      mrnumber = {2227728},
      mrreviewer = {Beatriz E. Viviani},
      doi = {10.1016/j.aim.2005.04.010},
      zblnumber = {1111.46008},
      }
  • [MW78] Go to document V. D. Milman and H. Wolfson, "Minkowski spaces with extremal distance from the Euclidean space," Israel J. Math., vol. 29, iss. 2-3, pp. 113-131, 1978.
    @ARTICLE{MW78,
      author = {Milman, V. D. and Wolfson, H.},
      title = {Minkowski spaces with extremal distance from the {E}uclidean space},
      journal = {Israel J. Math.},
      fjournal = {Israel Journal of Mathematics},
      volume = {29},
      year = {1978},
      number = {2-3},
      pages = {113--131},
      issn = {0021-2172},
      mrclass = {46B05},
      mrnumber = {0467255},
      mrreviewer = {M. I. Kadec},
      doi = {10.1007/BF02762002},
      zblnumber = {0374.46013},
      }
  • [Nao10] A. Naor, "$L_1$ embeddings of the Heisenberg group and fast estimation of graph isoperimetry," in Proceedings of the International Congress of Mathematicians. Volume III, 2010, pp. 1549-1575.
    @INPROCEEDINGS{Nao10,
      author = {Naor, Assaf},
      title = {{$L_1$} embeddings of the {H}eisenberg group and fast estimation of graph isoperimetry},
      booktitle = {Proceedings of the {I}nternational {C}ongress of {M}athematicians. {V}olume {III}},
      pages = {1549--1575},
      publisher = {Hindustan Book Agency, New Delhi},
      year = {2010},
      mrclass = {46-02 (46B80 46B85)},
      mrnumber = {2827855},
      zblnumber = {1232.46021},
      }
  • [Nao12] Go to document A. Naor, "An introduction to the Ribe program," Jpn. J. Math., vol. 7, iss. 2, pp. 167-233, 2012.
    @ARTICLE{Nao12,
      author = {Naor, Assaf},
      title = {An introduction to the {R}ibe program},
      journal = {Jpn. J. Math.},
      fjournal = {Japanese Journal of Mathematics},
      volume = {7},
      year = {2012},
      number = {2},
      pages = {167--233},
      issn = {0289-2316},
      mrclass = {46-02 (46B07 46B80 46B85)},
      mrnumber = {2995229},
      doi = {10.1007/s11537-012-1222-7},
      zblnumber = {1261.46013},
      }
  • [Nao14] Go to document A. Naor, "Comparison of metric spectral gaps," Anal. Geom. Metr. Spaces, vol. 2, pp. 1-52, 2014.
    @ARTICLE{Nao14,
      author = {Naor, Assaf},
      title = {Comparison of metric spectral gaps},
      journal = {Anal. Geom. Metr. Spaces},
      fjournal = {Analysis and Geometry in Metric Spaces},
      volume = {2},
      year = {2014},
      pages = {1--52},
      issn = {2299-3274},
      mrclass = {46B85 (05C12 05C50 15B51)},
      mrnumber = {3208067},
      mrreviewer = {Mikhail Ostrovskii},
      doi = {10.2478/agms-2014-0001},
      zblnumber = {1316.46023},
      }
  • [NPSS06] Go to document A. Naor, Y. Peres, O. Schramm, and S. Sheffield, "Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces," Duke Math. J., vol. 134, iss. 1, pp. 165-197, 2006.
    @ARTICLE{NPSS06,
      author = {Naor, Assaf and Peres, Yuval and Schramm, Oded and Sheffield, Scott},
      title = {Markov chains in smooth {B}anach spaces and {G}romov-hyperbolic metric spaces},
      journal = {Duke Math. J.},
      fjournal = {Duke Mathematical Journal},
      volume = {134},
      year = {2006},
      number = {1},
      pages = {165--197},
      issn = {0012-7094},
      mrclass = {46B09 (46B20 60B11 60J05)},
      mrnumber = {2239346},
      mrreviewer = {Keith Ball},
      doi = {10.1215/S0012-7094-06-13415-4},
      zblnumber = {1108.46012},
      }
  • [NRS05] Go to document A. Naor, Y. Rabani, and A. Sinclair, "Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs," J. Funct. Anal., vol. 227, iss. 2, pp. 273-303, 2005.
    @ARTICLE{NRS05,
      author = {Naor, Assaf and Rabani, Yuval and Sinclair, Alistair},
      title = {Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs},
      journal = {J. Funct. Anal.},
      fjournal = {Journal of Functional Analysis},
      volume = {227},
      year = {2005},
      number = {2},
      pages = {273--303},
      issn = {0022-1236},
      mrclass = {68R10 (05C80 51F99)},
      mrnumber = {2168076},
      mrreviewer = {G. Schechtman},
      doi = {10.1016/j.jfa.2005.04.003},
      zblnumber = {1104.68087},
      }
  • [NS11] Go to document A. Naor and L. Silberman, "Poincaré inequalities, embeddings, and wild groups," Compos. Math., vol. 147, iss. 5, pp. 1546-1572, 2011.
    @ARTICLE{NS11,
      author = {Naor, Assaf and Silberman, Lior},
      title = {Poincaré inequalities, embeddings, and wild groups},
      journal = {Compos. Math.},
      fjournal = {Compositio Mathematica},
      volume = {147},
      year = {2011},
      number = {5},
      pages = {1546--1572},
      issn = {0010-437X},
      mrclass = {20F65 (58E40)},
      mrnumber = {2834732},
      mrreviewer = {Alexander Fel\cprime shtyn},
      doi = {10.1112/S0010437X11005343},
      zblnumber = {1267.20057},
      }
  • [NY18] A. Naor and R. Young, Foliated corona decompositions and the ${L}_1$ distortion of balls in the $3$-dimensional Heisenberg group, ʊʊnote = preprint, 2018.
    @misc{NY18,
      author={Naor, Assaf and Young, Robert},
      title={Foliated corona decompositions and the ${L}_1$ distortion of balls in the $3$-dimensional {H}eisenberg group},
      note = {preprint},
      year = {2018},
     }
  • [NY17] Go to document A. Naor and R. Young, "The integrality gap of the Goemans-Linial SDP relaxation for sparsest cut is at least a constant multiple of $\sqrt{\log n}$," in STOC’17—Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2017, pp. 564-575.
    @INCOLLECTION{NY17,
      author = {Naor, Assaf and Young, Robert},
      title = {The integrality gap of the {G}oemans-{L}inial {SDP} relaxation for sparsest cut is at least a constant multiple of {$\sqrt{\log n}$}},
      booktitle = {S{TOC}'17---{P}roceedings of the 49th {A}nnual {ACM} {SIGACT} {S}ymposium on {T}heory of {C}omputing},
      pages = {564--575},
      publisher = {ACM, New York},
      year = {2017},
      mrclass = {90C27 (68W25 90C22)},
      mrnumber = {3678211},
      zblnumber = {1370.68235},
      doi = {10.1145/3055399.3055413},
      }
  • [Ost12] Go to document M. I. Ostrovskii, "Embeddability of locally finite metric spaces into Banach spaces is finitely determined," Proc. Amer. Math. Soc., vol. 140, iss. 8, pp. 2721-2730, 2012.
    @ARTICLE{Ost12,
      author = {Ostrovskii, M. I.},
      title = {Embeddability of locally finite metric spaces into {B}anach spaces is finitely determined},
      journal = {Proc. Amer. Math. Soc.},
      fjournal = {Proceedings of the Amer. Math. Soc.},
      volume = {140},
      year = {2012},
      number = {8},
      pages = {2721--2730},
      issn = {0002-9939},
      mrclass = {46B85 (46B08 46B20 54E35)},
      mrnumber = {2910760},
      mrreviewer = {Walden Freedman},
      doi = {10.1090/S0002-9939-2011-11272-3},
      zblnumber = {1276.46013},
      }
  • [Ost13] Go to document M. I. Ostrovskii, Metric Embeddings, De Gruyter, Berlin, 2013, vol. 49.
    @BOOK{Ost13,
      author = {Ostrovskii, Mikhail I.},
      title = {Metric Embeddings},
      series = {De Gruyter Stud. Math.},
      volume = {49},
      note = {Bilipschitz and coarse embeddings into {B}anach spaces},
      publisher = {De Gruyter, Berlin},
      year = {2013},
      pages = {xii+372},
      isbn = {978-3-11-026340-4; 978-3-11-026401-2},
      mrclass = {46-01 (46-02 46B20 46B85)},
      mrnumber = {3114782},
      mrreviewer = {Florent Baudier},
      doi = {10.1515/9783110264012},
      zblnumber = {1279.46001},
      }
  • [Pan82] P. Pansu, "Une inégalité isopérimétrique sur le groupe de Heisenberg," C. R. Acad. Sci. Paris Sér. I Math., vol. 295, iss. 2, pp. 127-130, 1982.
    @ARTICLE{Pan82,
      author = {Pansu, Pierre},
      title = {Une inégalité isopérimétrique sur le groupe de {H}eisenberg},
      journal = {C. R. Acad. Sci. Paris Sér. I Math.},
      fjournal = {Comptes Rendus des Séances de l'Académie des Sciences. Série I. Mathématique},
      volume = {295},
      year = {1982},
      number = {2},
      pages = {127--130},
      issn = {0249-6291},
      mrclass = {53C20 (22E25 53C65 58F17)},
      mrnumber = {0676380},
      zblnumber = {0502.53039},
      }
  • [Pan89] Go to document P. Pansu, "Métriques de Carnot-Carathéodory et quasiisométries des espaces symétriques de rang un," Ann. of Math. (2), vol. 129, iss. 1, pp. 1-60, 1989.
    @ARTICLE{Pan89,
      author = {Pansu, Pierre},
      title = {Métriques de {C}arnot-{C}arathéodory et quasiisométries des espaces symétriques de rang un},
      journal = {Ann. of Math. (2)},
      fjournal = {Annals of Mathematics. Second Series},
      volume = {129},
      year = {1989},
      number = {1},
      pages = {1--60},
      issn = {0003-486X},
      mrclass = {53C20 (22E40)},
      mrnumber = {0979599},
      mrreviewer = {Gudlaugur Thorbergsson},
      doi = {10.2307/1971484},
      zblnumber = {0678.53042},
      }
  • [Pis75] Go to document G. Pisier, "Martingales with values in uniformly convex spaces," Israel J. Math., vol. 20, iss. 3-4, pp. 326-350, 1975.
    @ARTICLE{Pis75,
      author = {Pisier, Gilles},
      title = {Martingales with values in uniformly convex spaces},
      journal = {Israel J. Math.},
      fjournal = {Israel Journal of Mathematics},
      volume = {20},
      year = {1975},
      number = {3-4},
      pages = {326--350},
      issn = {0021-2172},
      mrclass = {46B10 (60G45)},
      mrnumber = {0394135},
      mrreviewer = {S. D. Chatterji},
      doi = {10.1007/BF02760337},
      zblnumber = {0344.46030},
      }
  • [PX03] Go to document G. Pisier and Q. Xu, "Non-commutative $L^p$-Spaces," in Handbook of the Geometry of Banach spaces, Vol. 2, North-Holland, Amsterdam, 2003, pp. 1459-1517.
    @INCOLLECTION{PX03,
      author = {Pisier, Gilles and Xu, Quanhua},
      title = {Non-commutative {$L^p$}-{S}paces},
      booktitle = {Handbook of the Geometry of {B}anach spaces, {V}ol. 2},
      pages = {1459--1517},
      publisher = {North-Holland, Amsterdam},
      year = {2003},
      mrclass = {46L52 (46L51)},
      mrnumber = {1999201},
      mrreviewer = {Narcisse Randrianantoanina},
      doi = {10.1016/S1874-5849(03)80041-4},
      zblnumber = {1046.46048},
      }
  • [Rao99] Go to document S. Rao, "Small distortion and volume preserving embeddings for planar and Euclidean metrics," in Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999, pp. 300-306.
    @INPROCEEDINGS{Rao99,
      author = {Rao, Satish},
      title = {Small distortion and volume preserving embeddings for planar and {E}uclidean metrics},
      booktitle = {Proceedings of the {F}ifteenth {A}nnual {S}ymposium on {C}omputational {G}eometry},
      venue = {{M}iami {B}each, {FL},
      1999},
      pages = {300--306},
      publisher = {ACM, New York},
      year = {1999},
      mrclass = {54E35 (52B55 68U05 68W25)},
      mrnumber = {1802217},
      doi = {10.1145/304893.304983},
      zblnumber = {},
      }
  • [Shm95] D. B. Shmoys, "Cut problems and their application to divide-and-conquer," in Approximation Algorithms for $\mathrm{NP}$-hard Problems, PWS Publishing Co., Boston, MA, 1997, pp. 192-235.
    @INCOLLECTION{Shm95,
      author = {Shmoys, D. B.},
      title = {Cut problems and their application to divide-and-conquer},
      booktitle = {Approximation Algorithms for $\mathrm{NP}$-hard Problems},
      note = {Chapter 5, D.S. Hochbaum, ed.},
      pages = {192--235},
      publisher = {PWS Publishing Co., Boston, MA},
      year = {1997},
      zblnumber = {},
      }
  • [JS89] Go to document A. Sinclair and M. Jerrum, "Approximate counting, uniform generation and rapidly mixing Markov chains," Inform. and Comput., vol. 82, iss. 1, pp. 93-133, 1989.
    @ARTICLE{JS89,
      author = {Sinclair, Alistair and Jerrum, Mark},
      title = {Approximate counting, uniform generation and rapidly mixing {M}arkov chains},
      journal = {Inform. and Comput.},
      fjournal = {Information and Computation},
      volume = {82},
      year = {1989},
      number = {1},
      pages = {93--133},
      issn = {0890-5401},
      mrclass = {68Q25 (60J10 68R05 68R10)},
      mrnumber = {1003059},
      doi = {10.1016/0890-5401(89)90067-9},
      zblnumber = {0668.05060},
      }
  • [SM90] Go to document F. Shahrokhi and D. W. Matula, "The maximum concurrent flow problem," J. Assoc. Comput. Mach., vol. 37, iss. 2, pp. 318-334, 1990.
    @ARTICLE{SM90,
      author = {Shahrokhi, Farhad and Matula, D. W.},
      title = {The maximum concurrent flow problem},
      journal = {J. Assoc. Comput. Mach.},
      fjournal = {Journal of the Association for Computing Machinery},
      volume = {37},
      year = {1990},
      number = {2},
      pages = {318--334},
      issn = {0004-5411},
      mrclass = {90B10},
      mrnumber = {1072261},
      doi = {10.1145/77600.77620},
      zblnumber = {0696.68071},
      }
  • [Tes08] Go to document R. Tessera, "Quantitative property A, Poincaré inequalities, $L^p$-compression and $L^p$-distortion for metric measure spaces," Geom. Dedicata, vol. 136, pp. 203-220, 2008.
    @ARTICLE{Tes08,
      author = {Tessera, Romain},
      title = {Quantitative property {A},
      {P}oincaré inequalities, {$L^p$}-compression and {$L^p$}-distortion for metric measure spaces},
      journal = {Geom. Dedicata},
      fjournal = {Geometriae Dedicata},
      volume = {136},
      year = {2008},
      pages = {203--220},
      issn = {0046-5755},
      mrclass = {51F99 (43A85 46B20)},
      mrnumber = {2443353},
      mrreviewer = {Jeremy T. Tyson},
      doi = {10.1007/s10711-008-9286-5},
      zblnumber = {1162.46043},
      }
  • [Tre12] Go to document L. Trevisan, "On Khot’s unique games conjecture," Bull. Amer. Math. Soc. (N.S.), vol. 49, iss. 1, pp. 91-111, 2012.
    @ARTICLE{Tre12,
      author = {Trevisan, Luca},
      title = {On {K}hot's unique games conjecture},
      journal = {Bull. Amer. Math. Soc. (N.S.)},
      fjournal = {Amer. Math. Soc.. Bulletin. New Series},
      volume = {49},
      year = {2012},
      number = {1},
      pages = {91--111},
      issn = {0273-0979},
      mrclass = {68Q17 (68Q15)},
      mrnumber = {2869009},
      mrreviewer = {Frederic Green},
      doi = {10.1090/S0273-0979-2011-01361-1},
      zblnumber = {1280.68102},
      }
  • [Woj91] Go to document P. Wojtaszczyk, Banach Spaces for Analysts, Cambridge University Press, Cambridge, 1991, vol. 25.
    @BOOK{Woj91,
      author = {Wojtaszczyk, P.},
      title = {Banach Spaces for Analysts},
      series = {Cambridge Stud. Adv. Math.},
      volume = {25},
      publisher = {Cambridge University Press, Cambridge},
      year = {1991},
      pages = {xiv+382},
      isbn = {0-521-35618-0},
      mrclass = {46-01 (30-01 43-01 46Bxx 46Exx 47Bxx)},
      mrnumber = {1144277},
      mrreviewer = {Raymond H. Cox},
      doi = {10.1017/CBO9780511608735},
      zblnumber = {0724.46012},
      }
  • [WW75] Go to document J. H. Wells and L. R. Williams, Embeddings and Extensions in Analysis, Springer-Verlag, New York, 1975, vol. 84.
    @BOOK{WW75,
      author = {Wells, J. H. and Williams, L. R.},
      title = {Embeddings and Extensions in Analysis},
      note = {Ergeb. Math. Grenzgeb.},
      volume = {84},
      publisher = {Springer-Verlag, New York},
      year = {1975},
      pages = {vii+108},
      mrclass = {46C05 (46E30)},
      mrnumber = {0461107},
      mrreviewer = {S. P. Goyal},
      zblnumber = {0324.46034},
      doi = {10.1007/978-3-642-66037-5},
      }
  • [You16] Go to document R. Young, "Quantitative nonorientability of embedded cycles," Duke Math. J., vol. 167, iss. 1, pp. 41-108, 2018.
    @ARTICLE{You16,
      author = {Young, Robert},
      title = {Quantitative nonorientability of embedded cycles},
      journal = {Duke Math. J.},
      fjournal = {Duke Mathematical Journal},
      volume = {167},
      year = {2018},
      number = {1},
      pages = {41--108},
      issn = {0012-7094},
      mrclass = {49Q15 (53A07)},
      mrnumber = {3743699},
      doi = {10.1215/00127094-2017-0035},
      zblnumber = {06847242},
      }

Authors

Assaf Naor

Department of Mathematics, Princeton University, Princeton, NJ

Robert Young

New York University, Courant Institute of Mathematical Sciences, New York, NY