Vertical perimeter versus horizontal perimeter
DOI10.4007/annals.2018.188.1.4zbMath1397.46020arXiv1701.00620OpenAlexW2963766025WikidataQ105337446 ScholiaQ105337446MaRDI QIDQ1643390
Publication date: 19 June 2018
Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1701.00620
semidefinite programmingHeisenberg groupisoperimetric inequalityapproximation algorithmmetric embeddingsparsest cut problemmetric of negative type
Geometric group theory (20F65) Approximation algorithms (68W25) (L^p)-spaces and other function spaces on groups, semigroups, etc. (43A15) Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science (46B85) Geometric embeddings of metric spaces (30L05)
Related Items
Cites Work
- Markov type and threshold embeddings
- Sharp quantitative nonembeddability of the Heisenberg group into superreflexive Banach spaces
- Compression bounds for Lipschitz maps from the Heisenberg group to \(L_{1}\)
- A doubling subset of \(L_p\) for \(p>2\) that is inherently infinite dimensional
- Vertical versus horizontal Poincaré inequalities on the Heisenberg group
- Markov convexity and nonembeddability of the Heisenberg group
- Metric differentiation, monotonicity and maps to \(L^{1}\)
- Improved bounds in the metric cotype inequality for Banach spaces
- On the optimality of gluing over scales
- Differentiability of intrinsic Lipschitz functions within Heisenberg groups
- Rectifiable sets and the traveling salesman problem
- Quantitative property A, Poincaré inequalities, \(L^p\)-compression and \(L^p\)-distortion for metric measure spaces
- Differentiating maps into \(L^1\), and the geometry of BV functions
- On Lipschitz embedding of finite metric spaces in Hilbert space
- Approximate counting, uniform generation and rapidly mixing Markov chains
- Carnot-Carathéodory metrics and quasiisometries of symmetric spaces of rank 1
- Groups of polynomial growth and expanding maps. Appendix by Jacques Tits
- Wavelets and singular integrals on curves and surfaces
- Markov chains, Riesz transforms and Lipschitz maps
- Martingales with values in uniformly convex spaces
- Minkowski spaces with extremal distance from the Euclidean space
- Geometric algorithms and combinatorial optimization.
- Semidefinite programming in combinatorial optimization
- On the structure of finite perimeter sets in step 2 Carnot groups
- Quantitative nonorientability of embedded cycles
- On the distribution of the Fourier spectrum of Boolean functions
- The geometry of graphs and some of its algorithmic applications
- Markov convexity and local rigidity of distorted metrics
- An introduction to the Ribe program
- Metric embeddings. Bilipschitz and coarse embeddings into Banach spaces
- Coarse differentiation and quantitative nonembeddability for Carnot groups
- On the hardness of approximating Multicut and Sparsest-Cut
- Nonembeddability theorems via Fourier analysis
- Vector-valued Littlewood--Paley--Stein theory for semigroups
- Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces
- Metric structures in \(L_1\): dimension, snowflakes, and average distortion
- Measured descent: A new embedding method for finite metrics
- Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs
- Embeddability of locally finite metric spaces into Banach spaces is finitely determined
- Integrality gaps for sparsest cut and minimum linear arrangement problems
- Poincaré inequalities, embeddings, and wild groups
- L_1 embeddings of the Heisenberg group and fast estimation of graph isoperimetry
- On Khot’s unique games conjecture
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Opérateurs intégraux singuliers sur certaines courbes du plan complexe
- Polynomial flow-cut gaps and hardness of directed cut problems
- The maximum concurrent flow problem
- Metric Dichotomies
- On the power of unique 2-prover 1-round games
- A new proof of Gromov’s theorem on groups of polynomial growth
- Improved Lower Bounds for Embeddings into $L_1$
- Plongements lipschitziens dans ${\bbfR}\sp n$
- Séries de variables aléatoires vectorielles indépendantes et propriétés géométriques des espaces de Banach
- Ultraproducts in Banach space theory.
- Rectifiable Metric Spaces: Local Structure and Regularity of the Hausdorff Measure
- An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
- Sobolev met Poincaré
- Snowflake universality of Wasserstein spaces
- A T(b) theorem with remarks on analytic capacity and the Cauchy integral
- Extension of range of functions
- Word distance on the discrete Heisenberg group
- The integrality gap of the Goemans-Linial SDP relaxation for sparsest cut is at least a constant multiple of √log n
- A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP
- Bilu–Linial Stable Instances of Max Cut and Minimum Multiway Cut
- Comparison of Metric Spectral Gaps
- Near-optimal distortion bounds for embedding doubling spaces into L 1
- Euclidean distortion and the sparsest cut
- Embeddings of locally finite metric spaces into Banach spaces
- A PRG for lipschitz functions of polynomials with applications to sparsest cut
- The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1
- The Degree of Polynomial Growth of Finitely Generated Nilpotent Groups
- [https://portal.mardi4nfdi.de/wiki/Publication:5689214 Isoperimetric and Sobolev inequalities for Carnot-Carath�odory spaces and the existence of minimal surfaces]
- Expander flows, geometric embeddings and graph partitioning
- Trees and Markov convexity
- Geometry of cuts and metrics
- Some fine properties of sets of finite perimeter in Ahlfors regular metric measure spaces
- Rectifiability and perimeter in the Heisenberg group
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item