Vertical perimeter versus horizontal perimeter
type: Item
instance of: scholarly article
title: Vertical perimeter versus horizontal perimeter
zbMATH Open document ID: 1397.46020
author: Assaf Naor
author: Robert Young
published in: Annals of Mathematics. Second Series
publication date: 2018-06-19T00:00:00Z
full work available at URL: https://arxiv.org/abs/1701.00620
review text: 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 [\textit{F. Shahrokhi} and \textit{D. W. Matula}, J. Assoc. Comput. Mach. 37, No. 2, 318--334 (1990; Zbl 0696.68071)]). The Goemans-Linial semidefinite approximation algorithm, see [\textit{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 [\textit{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 \textit{J. R. Lee} and \textit{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; \url{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 \textit{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 absol…
Mathematics Subject Classification ID: 46B85
Mathematics Subject Classification ID: 20F65
Mathematics Subject Classification ID: 30L05
Mathematics Subject Classification ID: 43A15
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 6890812
zbMATH Keywords: approximation algorithm
zbMATH Keywords: Heisenberg group
zbMATH Keywords: isoperimetric inequality
zbMATH Keywords: metric embedding
zbMATH Keywords: metric of negative type
zbMATH Keywords: semidefinite programming
zbMATH Keywords: sparsest cut problem
Wikidata QID: Q105337446
reviewed by: Mikhail Ostrovskii
MaRDI profile type: Publication
OpenAlex ID: W2963766025
arXiv ID: 1701.00620
cites work: Q4954179
cites work: Euclidean distortion and the sparsest cut
cites work: Some fine properties of sets of finite perimeter in Ahlfors regular metric measure spaces
cites work: Snowflake universality of Wasserstein spaces
cites work: Sharp quantitative nonembeddability of the Heisenberg group into superreflexive Banach spaces
cites work: An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
cites work: Expander flows, geometric embeddings and graph partitioning
cites work: Plongements lipschitziens dans ${\bbfR}\sp n$
cites work: Markov chains, Riesz transforms and Lipschitz maps
cites work: Q5417101
cites work: The Degree of Polynomial Growth of Finitely Generated Nilpotent Groups
cites work: A course in metric geometry
cites work: Q4938152
cites work: Embeddings of locally finite metric spaces into Banach spaces
cites work: Word distance on the discrete Heisenberg group
cites work: On Lipschitz embedding of finite metric spaces in Hilbert space
cites work: On the distribution of the Fourier spectrum of Boolean functions
cites work: Q5657180
cites work: Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut
cites work: A T(b) theorem with remarks on analytic capacity and the Cauchy integral
cites work: Q5439813
cites work: Q3549612
cites work: Polynomial flow-cut gaps and hardness of directed cut problems
cites work: Differentiating maps into \(L^1\), and the geometry of BV functions
cites work: Metric differentiation, monotonicity and maps to \(L^{1}\)
cites work: On the hardness of approximating Multicut and Sparsest-Cut
cites work: A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP
cites work: Compression bounds for Lipschitz maps from the Heisenberg group to \(L_{1}\)
cites work: Opérateurs intégraux singuliers sur certaines courbes du plan complexe
cites work: Wavelets and singular integrals on curves and surfaces
cites work: Integrality gaps for sparsest cut and minimum linear arrangement problems
cites work: Geometry of cuts and metrics
cites work: Markov type and threshold embeddings
cites work: Q4001787
cites work: Q4278678
cites work: Q3129869
cites work: Rectifiability and perimeter in the Heisenberg group
cites work: On the structure of finite perimeter sets in step 2 Carnot groups
cites work: Q3425550
cites work: Differentiability of intrinsic Lipschitz functions within Heisenberg groups
cites work: Geometric algorithms and combinatorial optimization.
cites work: Isoperimetric and Sobolev inequalities for Carnot-Carath�odory spaces and the existence of minimal surfaces
cites work: Semidefinite programming in combinatorial optimization
cites work: Groups of polynomial growth and expanding maps. Appendix by Jacques Tits
cites work: Q4718347
cites work: Ultraproducts in Banach space theory.
cites work: Sobolev met Poincaré
cites work: On the optimality of gluing over scales
cites work: Q3829789
cites work: Rectifiable sets and the traveling salesman problem
cites work: Q3258063
cites work: On the power of unique 2-prover 1-round games

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Q3096713

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Rectifiable Metric Spaces: Local Structure and Regularity of the Hausdorff Measure

Vertical perimeter versus horizontal perimeter (cites work)
cites work: A new proof of Gromov’s theorem on groups of polynomial growth

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Measured descent: A new embedding method for finite metrics

Vertical perimeter versus horizontal perimeter (cites work)
cites work: A PRG for lipschitz functions of polynomials with applications to sparsest cut

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Nonembeddability theorems via Fourier analysis

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Improved Lower Bounds for Embeddings into $L_1$

Vertical perimeter versus horizontal perimeter (cites work)
cites work: The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1

Vertical perimeter versus horizontal perimeter (cites work)
cites work: On distance scales, embeddings, and efficient relaxations of the cut cone

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Coarse differentiation and quantitative nonembeddability for Carnot groups

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Markov convexity and nonembeddability of the Heisenberg group

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Q4549227

Vertical perimeter versus horizontal perimeter (cites work)
cites work: The geometry of graphs and some of its algorithmic applications

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Metric structures in \(L_1\): dimension, snowflakes, and average distortion

Vertical perimeter versus horizontal perimeter (cites work)
cites work: A doubling subset of \(L_p\) for \(p>2\) that is inherently infinite dimensional

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Vertical versus horizontal Poincaré inequalities on the Heisenberg group

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Trees and Markov convexity

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Near-optimal distortion bounds for embedding doubling spaces into L 1

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Q4530626

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Q4440809

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Extension of range of functions

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Metric Dichotomies

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Bilu–Linial Stable Instances of Max Cut and Minimum Multiway Cut

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Improved bounds in the metric cotype inequality for Banach spaces

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Markov convexity and local rigidity of distorted metrics

Vertical perimeter versus horizontal perimeter (cites work)
cites work: A tour of subriemannian geometries, their geodesics and applications

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Q3418237

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Séries de variables aléatoires vectorielles indépendantes et propriétés géométriques des espaces de Banach

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Vector-valued Littlewood--Paley--Stein theory for semigroups

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Minkowski spaces with extremal distance from the Euclidean space

Vertical perimeter versus horizontal perimeter (cites work)
cites work: L_1 embeddings of the Heisenberg group and fast estimation of graph isoperimetry

Vertical perimeter versus horizontal perimeter (cites work)
cites work: An introduction to the Ribe program

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Comparison of Metric Spectral Gaps

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Poincaré inequalities, embeddings, and wild groups

Vertical perimeter versus horizontal perimeter (cites work)
cites work: The integrality gap of the Goemans-Linial SDP relaxation for sparsest cut is at least a constant multiple of √log n

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Embeddability of locally finite metric spaces into Banach spaces is finitely determined

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Metric embeddings. Bilipschitz and coarse embeddings into Banach spaces

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Q3968106

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Carnot-Carathéodory metrics and quasiisometries of symmetric spaces of rank 1

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Martingales with values in uniformly convex spaces

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Q4440813

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Approximate counting, uniform generation and rapidly mixing Markov chains

Vertical perimeter versus horizontal perimeter (cites work)
cites work: The maximum concurrent flow problem

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Quantitative property A, Poincaré inequalities, \(L^p\)-compression and \(L^p\)-distortion for metric measure spaces

Vertical perimeter versus horizontal perimeter (cites work)
cites work: On Khot’s unique games conjecture

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Q3995204

Vertical perimeter versus horizontal perimeter (cites work)
cites work: Quantitative nonorientability of embedded cycles

Vertical perimeter versus horizontal perimeter (DOI)
DOI: 10.4007/ANNALS.2018.188.1.4