BZPEER

preprint2023arXiv

An integer parallelotope with small surface area

We prove that for any $n\in \mathbb{N}$ there is a convex body $K\subseteq \mathbb{R}^n$ whose surface area is at most $n^{\frac12+o(1)}$ , yet the translates of $K$ by the integer lattice $\mathbb{Z}^n$ tile $\mathbb{R}^n$ .

preprint2022arXiv

Cayley graphs that have a quantum ergodic eigenbasis

We investigate which finite Cayley graphs admit a quantum ergodic eigenbasis, proving that this holds for any Cayley graph on a group of size $n$ for which the sum of the dimensions of its irreducible representations is $o(n)$ , yet there exist Cayley graphs that do not have any quantum ergodic eigenbasis.

preprint2022arXiv

Efficient Rounding for the Noncommutative Grothendieck Inequality

$\newcommand{\cclass}[1]{\textsf{#1}}$ The classical Grothendieck inequality has applications to the design of approximation algorithms for $\cclass{NP}$-hard optimization problems. We show that an algorithmic interpretation may also be given for a noncommutative generalization of the Grothendieck inequality due to Pisier and Haagerup. Our main result, an efficient rounding procedure for this inequality, leads to a polynomial-time constant-factor approximation algorithm for an optimization problem which generalizes the Cut Norm problem of Frieze and Kannan, and is shown here to have additional applications to robust principal component analysis and the orthogonal Procrustes problem.

preprint2016arXiv

A spectral gap precludes low-dimensional embeddings

We prove that there is a universal constant $C>0$ with the following property. Suppose that $n\in \mathbb{N}$ and that $\mathsf{A}=(a_{ij})\in M_n(\mathbb{R})$ is a symmetric stochastic matrix. Denote the second-largest eigenvalue of $\mathsf{A}$ by $λ_2(\mathsf{A})$ . Then for $\mathrm{\it any}$ finite-dimensional normed space $(X,\|\cdot\|)$ we have $\forall\, x_1,\ldots,x_n\in X,\qquad \mathrm{dim}(X)\ge \frac12 \exp\left(C\frac{1-λ_2(\mathsf{A})}{\sqrt{n}}\bigg(\frac{\sum_{i=1}^n\sum_{j=1}^n\|x_i-x_j\|^2}{\sum_{i=1}^n\sum_{j=1}^na_{ij}\|x_i-x_j\|^2}\bigg)^{\frac12}\right).$ This implies that if an $n$ -vertex $O(1)$ -expander embeds with average distortion $D\ge 1$ into $X$ , then necessarily $\mathrm{dim}(X)\gtrsim n^{c/D}$ for some universal constant $c>0$ , thus improving over the previously best-known estimate $\mathrm{dim}(X)\gtrsim (\log n)^2/D^2$ of Linial, London and Rabinovich, strengthening a theorem of Matoušek, and answering a question of Andoni, Nikolov, Razenshteyn and Waingarten.

preprint2016arXiv

Discrete Riesz transforms and sharp metric $X_p$ inequalities

$ \renewcommand{\subset}{\subseteq} \newcommand{\N}{\mathbb N} $For $p\in [2,\infty)$ the metric $X_p$ inequality with sharp scaling parameter is proven here to hold true in $L_p$ . The geometric consequences of this result include the following sharp statements about embeddings of $L_q$ into $L_p$ when $2< q<p<\infty$ : the maximal $θ\in (0,1]$ for which $L_q$ admits a bi- $θ$ -Hölder embedding into $L_p$ equals $q/p$ , and for $m,n\in \N$ the smallest possible bi-Lipschitz distortion of any embedding into $L_p$ of the grid $\{1,\ldots,m\}^n\subset \ell_q^n$ is bounded above and below by constant multiples (depending only on $p,q$ ) of the quantity $\min\{n^{(p-q)(q-2)/(q^2(p-2))}, m^{(q-2)/q}\}$ .

preprint2016arXiv

Heat flow and quantitative differentiation

For every Banach space $(Y,\|\cdot\|_Y)$ that admits an equivalent uniformly convex norm we prove that there exists $c=c(Y)\in (0,\infty)$ with the following property. Suppose that $n\in \mathbb{N}$ and that $X$ is an $n$ -dimensional normed space with unit ball $B_X$ . Then for every $1$ -Lipschitz function $f:B_X\to Y$ and for every $\varepsilon\in (0,1/2]$ there exists a radius $r\ge\exp(-1/\varepsilon^{cn})$ , a point $x\in B_X$ with $x+rB_X\subset B_X$ , and an affine mapping $Λ:X\to Y$ such that $\|f(y)-Λ(y)\|_Y\le \varepsilon r$ for every $y\in x+rB_X$ .

preprint2016arXiv

Restricted invertibility revisited

Suppose that $m,n\in \mathbb{N}$ and that $A:\mathbb{R}^m\to \mathbb{R}^n$ is a linear operator. It is shown here that if $k,r\in \mathbb{N}$ satisfy $k<r\le \mathrm{\bf rank(A)}$ then there exists a subset $σ\subseteq \{1,\ldots,m\}$ with $|σ|=k$ such that the restriction of $A$ to $\mathbb{R}^σ\subseteq \mathbb{R}^m$ is invertible, and moreover the operator norm of the inverse $A^{-1}:A(\mathbb{R}^σ)\to \mathbb{R}^m$ is at most a constant multiple of the quantity $\sqrt{mr/((r-k)\sum_{i=r}^m \mathsf{s}_i(A)^2)}$ , where $\mathsf{s}_1(A)\geqslant\ldots\geqslant \mathsf{s}_m(A)$ are the singular values of $A$ . This improves over a series of works, starting from the seminal Bourgain--Tzafriri Restricted Invertibility Principle, through the works of Vershynin, Spielman--Srivastava and Marcus--Spielman--Srivastava. In particular, this directly implies an improved restricted invertibility principle in terms of Schatten--von Neumann norms.

preprint2015arXiv

Bourgain's discretization theorem

Bourgain's discretization theorem asserts that there exists a universal constant $C\in (0,\infty)$ with the following property. Let $X,Y$ be Banach spaces with $\dim X=n$ . Fix $D\in (1,\infty)$ and set $δ= e^{-n^{Cn}}$ . Assume that $\mathcal N$ is a $δ$ -net in the unit ball of $X$ and that $\mathcal N$ admits a bi-Lipschitz embedding into $Y$ with distortion at most $D$ . Then the entire space $X$ admits a bi-Lipschitz embedding into $Y$ with distortion at most $CD$ . This mostly expository article is devoted to a detailed presentation of a proof of Bourgain's theorem. We also obtain an improvement of Bourgain's theorem in the important case when $Y=L_p$ for some $p\in [1,\infty)$ : in this case it suffices to take $δ= C^{-1}n^{-5/2}$ for the same conclusion to hold true. The case $p=1$ of this improved discretization result has the following consequence. For arbitrarily large $n\in \mathbb{N}$ there exists a family $\mathscr Y$ of $n$ -point subsets of ${1,...,n}^2\subseteq \mathbb{R}^2$ such that if we write $|\mathscr Y|= N$ then any $L_1$ embedding of $\mathscr Y$ , equipped with the Earthmover metric (a.k.a. transportation cost metric or minimumum weight matching metric) incurs distortion at least a constant multiple of $\sqrt{\log\log N}$ ; the previously best known lower bound for this problem was a constant multiple of $\sqrt{\log\log \log N}$ .

preprint2015arXiv

Metric ${X}_p$ inequalities

For every $p\in (0,\infty)$ we associate to every metric space $(X,d_X)$ a numerical invariant $\mathfrak{X}_p(X)\in [0,\infty]$ such that if $\mathfrak{X}_p(X)<\infty$ and a metric space $(Y,d_Y)$ admits a bi-Lipschitz embedding into $X$ then also $\mathfrak{X}_p(Y)<\infty$ . We prove that if $p,q\in (2,\infty)$ satisfy $q<p$ then $\mathfrak{X}_p(L_p)<\infty$ yet $\mathfrak{X}_p(L_q)=\infty$ . Thus our new bi-Lipschitz invariant certifies that $L_q$ does not admit a bi-Lipschitz embedding into $L_p$ when $2<q<p<\infty$ . This completes the long-standing search for bi-Lipschitz invariants that serve as an obstruction to the embeddability of $L_p$ spaces into each other, the previously understood cases of which were metric notions of type and cotype, which however fail to certify the nonembeddability of $L_q$ into $L_p$ when $2<q<p<\infty$ . Among the consequences of our results are new quantitative restrictions on the bi-Lipschitz embeddability into $L_p$ of snowflakes of $L_q$ and integer grids in $\ell_q^n$ , for $2<q<p<\infty$ . As a byproduct of our investigations, we also obtain results on the geometry of the Schatten $p$ trace class $S_p$ that are new even in the linear setting.

preprint2015arXiv

On Lipschitz extension from finite subsets

We prove that for every $n\in \mathbb{N}$ there exists a metric space $(X,d_X)$ , an $n$ -point subset $S\subseteq X$ , a Banach space $(Z,\|\cdot\|_Z)$ and a $1$ -Lipschitz function $f:S\to Z$ such that the Lipschitz constant of every function $F:X\to Z$ that extends $f$ is at least a constant multiple of $\sqrt{\log n}$ . This improves a bound of Johnson and Lindenstrauss. We also obtain the following quantitative counterpart to a classical extension theorem of Minty. For every $α\in (1/2,1]$ and $n\in \mathbb{N}$ there exists a metric space $(X,d_X)$ , an $n$ -point subset $S\subseteq X$ and a function $f:S\to \ell_2$ that is $α$ -Hölder with constant $1$ , yet the $α$ -Hölder constant of any $F:X\to \ell_2$ that extends $f$ satisfies $\|F\|_{\mathrm{Lip}(α)}\gtrsim (\log n)^{\frac{2α-1}{4α}}+\left(\frac{\log n}{\log\log n}\right)^{α^2-\frac12}.$ We formulate a conjecture whose positive solution would strengthen Ball's nonlinear Maurey extension theorem, serving as a far-reaching nonlinear version of a theorem of König, Retherford and Tomczak-Jaegermann. We explain how this conjecture would imply as special cases answers to longstanding open questions of Johnson and Lindenstrauss and Kalton.

preprint2015arXiv

Pythagorean powers of hypercubes

For $n\in \mathbb{N}$ consider the $n$ -dimensional hypercube as equal to the vector space $\mathbb{F}_2^n$ , where $\mathbb{F}_2$ is the field of size two. Endow $\mathbb{F}_2^n$ with the Hamming metric, i.e., with the metric induced by the $\ell_1^n$ norm when one identifies $\mathbb{F}_2^n$ with $\{0,1\}^n\subseteq \mathbb{R}^n$ . Denote by $\ell_2^n(\mathbb{F}_2^n)$ the $n$ -fold Pythagorean product of $\mathbb{F}_2^n$ , i.e., the space of all $x=(x_1,\ldots,x_n)\in \prod_{j=1}^n \mathbb{F}_2^n$ , equipped with the metric $\forall\, x,y\in \prod_{j=1}^n \mathbb{F}_2^n,\qquad d_{\ell_2^n(\mathbb{F}_2^n)}(x,y)= \sqrt{ \|x_1-y_1\|_1^2+\ldots+\|x_n-y_n\|_1^2}.$ It is shown here that the bi-Lipschitz distortion of any embedding of $\ell_2^n(\mathbb{F}_2^n)$ into $L_1$ is at least a constant multiple of $\sqrt{n}$ . This is achieved through the following new bi-Lipschitz invariant, which is a metric version of (a slight variant of) a linear inequality of Kwapie{ń} and Schütt (1989). Letting $\{e_{jk}\}_{j,k\in \{1,\ldots,n\}}$ denote the standard basis of the space of all $n$ by $n$ matrices $M_n(\mathbb{F}_2)$ , say that a metric space $(X,d_X)$ is a KS space if there exists $C=C(X)>0$ such that for every $n\in 2\mathbb{N}$ , every mapping $f:M_n(\mathbb{F}_2)\to X$ satisfies \begin{equation*}\label{eq:metric KS abstract} \frac{1}{n}\sum_{j=1}^n\mathbb{E}\left[d_X\Big(f\Big(x+\sum_{k=1}^ne_{jk}\Big),f(x)\Big)\right]\le C \mathbb{E}\left[d_X\Big(f\Big(x+\sum_{j=1}^ne_{jk_j}\Big),f(x)\Big)\right], \end{equation*} where the expectations above are with respect to $x\in M_n(\mathbb{F}_2)$ and $k=(k_1,\ldots,k_n)\in \{1,\ldots,n\}^n$ chosen uniformly at random. It is shown here that $L_1$ is a KS space (with $C= 2e^2/(e^2-1)$ , which is best possible), implying the above nonembeddability statement. Links to the Ribe program are discussed, as well as related open problems.

preprint2015arXiv

Snowflake universality of Wasserstein spaces

For $p\in (1,\infty)$ let $\mathscr{P}_p(\mathbb{R}^3)$ denote the metric space of all $p$ -integrable Borel probability measures on $\mathbb{R}^3$ , equipped with the Wasserstein $p$ metric $\mathsf{W}_p$ . We prove that for every $\varepsilon>0$ , every $θ\in (0,1/p]$ and every finite metric space $(X,d_X)$ , the metric space $(X,d_{X}^θ)$ embeds into $\mathscr{P}_p(\mathbb{R}^3)$ with distortion at most $1+\varepsilon$ . We show that this is sharp when $p\in (1,2]$ in the sense that the exponent $1/p$ cannot be replaced by any larger number. In fact, for arbitrarily large $n\in \mathbb{N}$ there exists an $n$ -point metric space $(X_n,d_n)$ such that for every $α\in (1/p,1]$ any embedding of the metric space $(X_n,d_n^α)$ into $\mathscr{P}_p(\mathbb{R}^3)$ incurs distortion that is at least a constant multiple of $(\log n)^{α-1/p}$ . These statements establish that there exists an Alexandrov space of nonnegative curvature, namely $\mathscr{P}_{\! 2}(\mathbb{R}^3)$ , with respect to which there does not exist a sequence of bounded degree expander graphs. It also follows that $\mathscr{P}_{\! 2}(\mathbb{R}^3)$ does not admit a uniform, coarse, or quasisymmetric embedding into any Banach space of nontrivial type. Links to several longstanding open questions in metric geometry are discussed, including the characterization of subsets of Alexandrov spaces, existence of expanders, the universality problem for $\mathscr{P}_{\! 2}(\mathbb{R}^k)$ , and the metric cotype dichotomy problem.

preprint2015arXiv

Uniform nonextendability from nets

It is shown that there exist Banach spaces $X,Y$ , a $1$ -net $\mathscr{N}$ of $X$ and a Lipschitz function $f:\mathscr{N}\to Y$ such that every $F:X\to Y$ that extends $f$ is not uniformly continuous.

preprint2014arXiv

Expanders with respect to Hadamard spaces and random graphs

It is shown that there exists a sequence of 3-regular graphs $\{G_n\}_{n=1}^\infty$ and a Hadamard space $X$ such that $\{G_n\}_{n=1}^\infty$ forms an expander sequence with respect to $X$ , yet random regular graphs are not expanders with respect to $X$ . This answers a question of \cite{NS11}. $\{G_n\}_{n=1}^\infty$ are also shown to be expanders with respect to random regular graphs, yielding a deterministic sublinear time constant factor approximation algorithm for computing the average squared distance in subsets of a random graph. The proof uses the Euclidean cone over a random graph, an auxiliary continuous geometric object that allows for the implementation of martingale methods.

preprint2014arXiv

Solution of the propeller conjecture in $\mathbb{R}^3$

It is shown that every measurable partition ${A_1,..., A_k}$ of $\mathbb{R}^3$ satisfies $\sum_{i=1}^k||\int_{A_i} xe^{-\frac12||x||_2^2}dx||_2^2\le 9π^2.\qquad(*)$ Let ${P_1,P_2,P_3}$ be the partition of $\mathbb{R}^2$ into $120^\circ$ sectors centered at the origin. The bound is sharp, with equality holding if $A_i=P_i\times \mathbb{R}$ for $i\in {1,2,3}$ and $A_i=\emptyset$ for $i\in \{4,...,k\}$ (up to measure zero corrections, orthogonal transformations and renumbering of the sets $\{A_1,...,A_k\}$ ). This settles positively the 3-dimensional Propeller Conjecture of Khot and Naor (FOCS 2008). The proof of reduces the problem to a finite set of numerical inequalities which are then verified with full rigor in a computer-assisted fashion. The main consequence (and motivation) of $(*)$ is complexity-theoretic: the Unique Games hardness threshold of the Kernel Clustering problem with $4 \times 4$ centered and spherical hypothesis matrix equals $\frac{2π}{3}$ .

preprint2013arXiv

A doubling subset of $L_p$ for $p>2$ that is inherently infinite dimensional

It is shown that for every $p\in (2,\infty)$ there exists a doubling subset of $L_p$ that does not admit a bi-Lipschitz embedding into $\R^k$ for any $k\in \N$ .

preprint2013arXiv

Comparison of metric spectral gaps

Let $A=(a_{ij})\in M_n(\R)$ be an $n$ by $n$ symmetric stochastic matrix. For $p\in [1,\infty)$ and a metric space $(X,d_X)$ , let $γ(A,d_X^p)$ be the infimum over those $γ\in (0,\infty]$ for which every $x_1,...,x_n\in X$ satisfy $\frac{1}{n^2} \sum_{i=1}^n\sum_{j=1}^n d_X(x_i,x_j)^p\le \fracγ{n}\sum_{i=1}^n\sum_{j=1}^n a_{ij} d_X(x_i,x_j)^p.$ Thus $γ(A,d_X^p)$ measures the magnitude of the {\em nonlinear spectral gap} of the matrix $A$ with respect to the kernel $d_X^p:X\times X\to [0,\infty)$ . We study pairs of metric spaces $(X,d_X)$ and $(Y,d_Y)$ for which there exists $Ψ:(0,\infty)\to (0,\infty)$ such that $γ(A,d_X^p)\le Ψ(γ(A,d_Y^p))$ for every symmetric stochastic $A\in M_n(\R)$ with $γ(A,d_Y^p)<\infty$ . When $Ψ$ is linear a complete geometric characterization is obtained. Our estimates on nonlinear spectral gaps yield new embeddability results as well as new nonembeddability results. For example, it is shown that if $n\in \N$ and $p\in (2,\infty)$ then for every $f_1,...,f_n\in L_p$ there exist $x_1,...,x_n\in L_2$ such that {equation}\label{eq:p factor} \forall\, i,j\in \{1,...,n\},\quad \|x_i-x_j\|_2\lesssim p\|f_i-f_j\|_p, {equation} and $\sum_{i=1}^n\sum_{j=1}^n \|x_i-x_j\|_2^2=\sum_{i=1}^n\sum_{j=1}^n \|f_i-f_j\|_p^2.$ This statement is impossible for $p\in [1,2)$ , and the asymptotic dependence on $p$ in \eqref{eq:p factor} is sharp. We also obtain the best known lower bound on the $L_p$ distortion of Ramanujan graphs, improving over the work of Matoušek. Links to Bourgain--Milman--Wolfson type and a conjectural nonlinear Maurey--Pisier theorem are studied.

preprint2013arXiv

Nonlinear spectral calculus and super-expanders

Nonlinear spectral gaps with respect to uniformly convex normed spaces are shown to satisfy a spectral calculus inequality that establishes their decay along Cesaro averages. Nonlinear spectral gaps of graphs are also shown to behave sub-multiplicatively under zigzag products. These results yield a combinatorial construction of super-expanders, i.e., a sequence of 3-regular graphs that does not admit a coarse embedding into any uniformly convex normed space.

preprint2013arXiv

Pisier's inequality revisited

Given a Banach space $X$ , for $n\in \mathbb N$ and $p\in (1,\infty)$ we investigate the smallest constant $\mathfrak P\in (0,\infty)$ for which every $f_1,...,f_n:{-1,1}^n\to X$ satisfy \int_{{-1,1}^n}\Bigg|\sum_{j=1}^n \partial_jf_j(\varepsilon)\Bigg|^pdμ(\varepsilon) \leq \mathfrak{P}^p\int_{{-1,1}^n}\int_{{-1,1}^n}\Bigg\|\sum_{j=1}^n \d_jΔf_j(\varepsilon)\Bigg\|^pdμ(\varepsilon) dμ(δ), where $μ$ is the uniform probability measure on the discrete hypercube ${-1,1}^n$ and ${\partial_j}_{j=1}^n$ and $Δ=\sum_{j=1}^n\partial_j$ are the hypercube partial derivatives and the hypercube Laplacian, respectively. Denoting this constant by $\mathfrak{P}_p^n(X)$ , we show that $\mathfrak{P}_p^n(X)\le \sum_{k=1}^{n}\frac{1}{k}$ for every Banach space $(X,|\cdot|)$ . This extends the classical Pisier inequality, which corresponds to the special case $f_j=Δ^{-1}\partial_j f$ for some $f:{-1,1}^n\to X$ . We show that $\sup_{n\in \N}\mathfrak{P}_p^n(X)<\infty$ if either the dual $X^*$ is a $\mathrm{UMD}^+$ Banach space, or for some $θ\in (0,1)$ we have $X=[H,Y]_θ$ , where $H$ is a Hilbert space and $Y$ is an arbitrary Banach space. It follows that $\sup_{n\in \N}\mathfrak{P}_p^n(X)<\infty$ if $X$ is a Banach lattice of finite cotype.

preprint2013arXiv

Spectral calculus and Lipschitz extension for barycentric metric spaces

The metric Markov cotype of barycentric metric spaces is computed, yielding the first class of metric spaces that are not Banach spaces for which this bi-Lipschitz invariant is understood. It is shown that this leads to new nonlinear spectral calculus inequalities, as well as a unified framework for Lipschitz extension, including new Lipschitz extension results for CAT(0) targets. An example that elucidates the relation between metric Markov cotype and Rademacher cotype is analyzed, showing that a classical Lipschitz extension theorem of Johnson, Lindenstrauss and Benyamini is asymptotically sharp.

preprint2012arXiv

An introduction to the Ribe program

This article accompanies the 10th Takagi Lectures, delivered by the author at RIMS, Kyoto, on May 26 2012. It contains an exposition of results, applications, and challenges of the Ribe program.

preprint2012arXiv

Discretization and affine approximation in high dimensions

Lower estimates are obtained for the macroscopic scale of affine approximability of vector-valued Lipschitz functions on finite dimensional normed spaces, completing the work of Bates, Johnson, Lindenstrass, Preiss and Schechtman. This yields a new approach to Bourgain's discretization theorem for superreflexive targets.

preprint2012arXiv

Krivine schemes are optimal

It is shown that for every $k\in \N$ there exists a Borel probability measure $μ$ on $\{-1,1\}^{\R^{k}}\times \{-1,1\}^{\R^{k}}$ such that for every $m,n\in \N$ and $x_1,..., x_m,y_1,...,y_n\in S^{m+n-1}$ there exist $x_1',...,x_m',y_1',...,y_n'\in S^{m+n-1}$ such that if $G:\R^{m+n}\to \R^k$ is a random $k\times (m+n)$ matrix whose entries are i.i.d. standard Gaussian random variables then for all $(i,j)\in {1,...,m}\times {1,...,n}$ we have \E_G[\int_{{-1,1}^{\R^{k}}\times {-1,1}^{\R^{k}}}f(Gx_i')g(Gy_j')dμ(f,g)]=\frac{<x_i,y_j>}{(1+C/k)K_G}, where $K_G$ is the real Grothendieck constant and $C\in (0,\infty)$ is a universal constant. This establishes that Krivine's rounding method yields an arbitrarily good approximation of $K_G$ .

preprint2012arXiv

Locally decodable codes and the failure of cotype for projective tensor products

It is shown that for every $p\in (1,\infty)$ there exists a Banach space $X$ of finite cotype such that the projective tensor product $\ell_p\tp X$ fails to have finite cotype. More generally, if $p_1,p_2,p_3\in (1,\infty)$ satisfy $\frac{1}{p_1}+\frac{1}{p_2}+\frac{1}{p_3}\le 1$ then $\ell_{p_1}\tp\ell_{p_2}\tp\ell_{p_3}$ does not have finite cotype. This is a proved via a connection to the theory of locally decodable codes.

preprint2012arXiv

Ultrametric subsets with large Hausdorff dimension

It is shown that for every $\e\in (0,1)$, every compact metric space $(X,d)$ has a compact subset $S\subseteq X$ that embeds into an ultrametric space with distortion $O(1/\e)$, and $$\dim_H(S)\ge (1-\e)\dim_H(X),$$ where $\dim_H(\cdot)$ denotes Hausdorff dimension. The above $O(1/\e)$ distortion estimate is shown to be sharp via a construction based on sequences of expander graphs.

preprint2012arXiv

Vertical versus horizontal Poincaré inequalities on the Heisenberg group

Let $\H= < a,b | a[a,b]=[a,b]a \wedge b[a,b]=[a,b]b>$ be the discrete Heisenberg group, equipped with the left-invariant word metric $d_W(\cdot,\cdot)$ associated to the generating set ${a,b,a^{-1},b^{-1}}$ . Letting $B_n= {x\in \H: d_W(x,e_\H)\le n}$ denote the corresponding closed ball of radius $n\in \N$ , and writing $c=[a,b]=aba^{-1}b^{-1}$ , we prove that if $(X,|\cdot|_X)$ is a Banach space whose modulus of uniform convexity has power type $q\in [2,\infty)$ then there exists $K\in (0,\infty)$ such that every $f:\H\to X$ satisfies {multline*} \sum_{k=1}^{n^2}\sum_{x\in B_n}\frac{|f(xc^k)-f(x)|_X^q}{k^{1+q/2}}\le K\sum_{x\in B_{21n}} \Big(|f(xa)-f(x)|^q_X+\|f(xb)-f(x)\|^q_X\Big). {multline*} It follows that for every $n\in \N$ the bi-Lipschitz distortion of every $f:B_n\to X$ is at least a constant multiple of $(\log n)^{1/q}$ , an asymptotically optimal estimate as $n\to\infty$ .

preprint2011arXiv

A note on dichotomies for metric transforms

We show that for every nondecreasing concave function w:R+ --> R+ with w(0)=0, either every finite metric space embeds with distortion arbitrarily close to 1 into a metric space of the form (X,w o d) for some metric d on X, or there exists a=a(w)>0 and n_0=n_0(w)\in N such that for all n>n_0, any embedding of {0,...,n} into a metric space of the form (X,w o d) incurs distortion at least n^a.

preprint2011arXiv

Grothendieck-type inequalities in combinatorial optimization

We survey connections of the Grothendieck inequality and its variants to combinatorial optimization and computational complexity.

preprint2011arXiv

Metric Cotype

We introduce the notion of cotype of a metric space, and prove that for Banach spaces it coincides with the classical notion of Rademacher cotype. This yields a concrete version of Ribe's theorem, settling a long standing open problem in the nonlinear theory of Banach spaces. We apply our results to several problems in metric geometry. Namely, we use metric cotype in the study of uniform and coarse embeddings, settling in particular the problem of classifying when L_p coarsely or uniformly embeds into L_q. We also prove a nonlinear analog of the Maurey-Pisier theorem, and use it to answer a question posed by Arora, Lovasz, Newman, Rabani, Rabinovich and Vempala, and to obtain quantitative bounds in a metric Ramsey theorem due to Matousek.

preprint2011arXiv

Sparse quadratic forms and their geometric applications (after Batson, Spielman and Srivastava)

We survey the work of Batson, Spielman and Srivastava on graph sparsification, and we describe some of its recently discovered geometric applications.

preprint2011arXiv

The Grothendieck constant is strictly smaller than Krivine's bound

We prove that $K_G<\fracπ{2\log(1+\sqrt{2})}$ , where $K_G$ is the Grothendieck constant.

preprint2011arXiv

Ultrametric skeletons

We prove that for every $ε\in (0,1)$ there exists $C_ε\in (0,\infty)$ with the following property. If $(X,d)$ is a compact metric space and $μ$ is a Borel probability measure on $X$ then there exists a compact subset $S\subseteq X$ that embeds into an ultrametric space with distortion $O(1/ε)$ , and a probability measure $ν$ supported on $S$ satisfying $ν(B_d(x,r))\le (μ(B_d(x,C_εr))^{1-ε}$ for all $x\in X$ and $r\in (0,\infty)$ . The dependence of the distortion on $ε$ is sharp. We discuss an extension of this statement to multiple measures, as well as how it implies Talagrand's majorizing measures theorem.

preprint2010arXiv

Absolutely minimal Lipschitz extension of tree-valued mappings

We prove that every Lipschitz function from a subset of a locally compact length space to a metric tree has a unique absolutely minimal Lipschitz extension (AMLE). We relate these extensions to a stochastic game called {\bf Politics} - a generalization of a game called {\bf Tug of War} that has been used in \cite{PSSW09} to study real-valued AMLEs.

preprint2010arXiv

Assouad's theorem with dimension independent of the snowflaking

It is shown that for every $K>0$ and $\e\in (0,1/2)$ there exist $N=N(K)\in \N$ and $D=D(K,\e)\in (1,\infty)$ with the following properties. For every separable metric space $(X,d)$ with doubling constant at most $K$ , the metric space $(X,d^{1-\e})$ admits a bi-Lipschitz embedding into $\R^N$ with distortion at most $D$ . The classical Assouad embedding theorem makes the same assertion, but with $N\to \infty$ as $\e\to 0$.

preprint2010arXiv

Improved bounds in the metric cotype inequality for Banach spaces

It is shown that if (X, ||.||_X) is a Banach space with Rademacher cotype q then for every integer n there exists an even integer m< n^{1+1/q} $such that for every f:Z_m^n --> X we have$ \sum_{j=1}^n \Avg_x [ ||f(x+ (m/2) e_j)-f(x) ||_X^q ] < C m^q \Avg_{\e,x} [ ||f(x+\e)-f(x) ||_X^q ]$, where the expectations are with respect to uniformly chosen x\in Z_m^n and \e\in \{-1,0,1\}^n, and all the implied constants may depend only on q and the Rademacher cotype q constant of X. This improves the bound of m< n^{2+\frac{1}{q}} from [Mendel, Naor 2008]. The proof of the above inequality is based on a "smoothing and approximation" procedure which simplifies the proof of the metric characterization of Rademacher cotype of [Mendel, Naor 2008]. We also show that any such "smoothing and approximation" approach to metric cotype inequalities must require m> n^{(1/2)+(1/q)}.

preprint2010arXiv

Improved bounds in the scaled Enflo type inequality for Banach spaces

It is shown that if (X,||.||_X) is a Banach space with Rademacher type p \ge 1, then for every integer n there exists an even integer m < Cn^{2-1/p}log n (C is an absolute constant), such that for every f:Z_m^n --> X, \Avg_{x,\e}[||f(x+ m\e/2)-f(x)}||_X^p] < C(p,X) m^p\sum_{j=1}^n\Avg_x[||f(x+e_j)-f(x)||_X^p], where the expectation is with respect to uniformly chosen x \in Z_m^n and \e \in \{-1,1\}^n, and C(p,X) is a constant that depends on p and the Rademacher type constant of X. This improves a bound of m < Cn^{3-2/p} that was obtained in [Mendel, Naor 2007]. The proof is based on an augmentation of the "smoothing and approximation" scheme, which was implicit in [Mendel, Naor 2007].

preprint2010arXiv

L_1 embeddings of the Heisenberg group and fast estimation of graph isoperimetry

We survey connections between the theory of bi-Lipschitz embeddings and the Sparsest Cut Problem in combinatorial optimization. The story of the Sparsest Cut Problem is a striking example of the deep interplay between analysis, geometry, and probability on the one hand, and computational issues in discrete mathematics on the other. We explain how the key ideas evolved over the past 20 years, emphasizing the interactions with Banach space theory, geometric measure theory, and geometric group theory. As an important illustrative example, we shall examine recently established connections to the the structure of the Heisenberg group, and the incompatibility of its Carnot-Carathéodory geometry with the geometry of the Lebesgue space $L_1$ .

preprint2010arXiv

Markov convexity and local rigidity of distorted metrics

It is shown that a Banach space admits an equivalent norm whose modulus of uniform convexity has power-type p if and only if it is Markov p-convex. Counterexamples are constructed to natural questions related to isomorphic uniform convexity of metric spaces, showing in particular that tree metrics fail to have the dichotomy property.

preprint2010arXiv

Maximum gradient embeddings and monotone clustering

Let (X,d_X) be an n-point metric space. We show that there exists a distribution D over non-contractive embeddings into trees f:X-->T such that for every x in X, the expectation with respect to D of the maximum over y in X of the ratio d_T(f(x),f(y)) / d_X(x,y) is at most C (log n)^2, where C is a universal constant. Conversely we show that the above quadratic dependence on log n cannot be improved in general. Such embeddings, which we call maximum gradient embeddings, yield a framework for the design of approximation algorithms for a wide range of clustering problems with monotone costs, including fault-tolerant versions of k-median and facility location.

preprint2010arXiv

On the Banach space valued Azuma inequality and small set isoperimetry of Alon-Roichman graphs

We discuss the connection between the expansion of small sets in graphs, and the Schatten norms of their adjacency matrix. In conjunction with a variant of the Azuma inequality for uniformly smooth normed spaces, we deduce improved bounds on the small set isoperimetry of Abelian Alon-Roichman random Cayley graphs.

preprint2010arXiv

Overlap properties of geometric expanders

The {\em overlap number} of a finite $(d+1)$ -uniform hypergraph $H$ is defined as the largest constant $c(H)\in (0,1]$ such that no matter how we map the vertices of $H$ into $\R^d$ , there is a point covered by at least a $c(H)$ -fraction of the simplices induced by the images of its hyperedges. In~\cite{Gro2}, motivated by the search for an analogue of the notion of graph expansion for higher dimensional simplicial complexes, it was asked whether or not there exists a sequence $\{H_n\}_{n=1}^\infty$ of arbitrarily large $(d+1)$ -uniform hypergraphs with bounded degree, for which $\inf_{n\ge 1} c(H_n)>0$ . Using both random methods and explicit constructions, we answer this question positively by constructing infinite families of $(d+1)$ -uniform hypergraphs with bounded degree such that their overlap numbers are bounded from below by a positive constant $c=c(d)$ . We also show that, for every $d$ , the best value of the constant $c=c(d)$ that can be achieved by such a construction is asymptotically equal to the limit of the overlap numbers of the complete $(d+1)$ -uniform hypergraphs with $n$ vertices, as $n\rightarrow\infty$ . For the proof of the latter statement, we establish the following geometric partitioning result of independent interest. For any $d$ and any $ε>0$ , there exists $K=K(ε,d)\ge d+1$ satisfying the following condition. For any $k\ge K$ , for any point $q \in \mathbb{R}^d$ and for any finite Borel measure $μ$ on $\mathbb{R}^d$ with respect to which every hyperplane has measure $0$ , there is a partition $\mathbb{R}^d=A_1 \cup \ldots \cup A_{k}$ into $k$ measurable parts of equal measure such that all but at most an $ε$ -fraction of the $(d+1)$ -tuples $A_{i_1},\ldots,A_{i_{d+1}}$ have the property that either all simplices with one vertex in each $A_{i_j}$ contain $q$ or none of these simplices contain $q$ .

preprint2010arXiv

Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem

We introduce a randomized iterative fragmentation procedure for finite metric spaces, which is guaranteed to result in a polynomially large subset that is $D$ -equivalent to an ultrametric, where $D\in (2,\infty)$ is a prescribed target distortion. Since this procedure works for $D$ arbitrarily close to the nonlinear Dvoretzky phase transition at distortion 2, we thus obtain a much simpler probabilistic proof of the main result of Bartel, Linial, Mendel, and Naor, answering a question from Mendel and Naor, and yielding the best known bounds in the nonlinear Dvoretzky theorem. Our method utilizes a sequence of random scales at which a given metric space is fragmented. As in many previous randomized arguments in embedding theory, these scales are chosen irrespective of the geometry of the metric space in question. We show that our bounds are sharp if one utilizes such a "scale-oblivious" fragmentation procedure.

preprint2010arXiv

Sharp quantitative nonembeddability of the Heisenberg group into superreflexive Banach spaces

Let $\H$ denote the discrete Heisenberg group, equipped with a word metric $d_W$ associated to some finite symmetric generating set. We show that if $(X,\|\cdot\|)$ is a $p$ -convex Banach space then for any Lipschitz function $f:\H\to X$ there exist $x,y\in \H$ with $d_W(x,y)$ arbitrarily large and \begin{equation}\label{eq:comp abs} \frac{\|f(x)-f(y)\|}{d_W(x,y)}\lesssim \left(\frac{\log\log d_W(x,y)}{\log d_W(x,y)}\right)^{1/p}. \end{equation} We also show that any embedding into $X$ of a ball of radius $R\ge 4$ in $\H$ incurs bi-Lipschitz distortion that grows at least as a constant multiple of \begin{equation}\label{eq:dist abs} \left(\frac{\log R}{\log\log R}\right)^{1/p}. \end{equation} Both~\eqref{eq:comp abs} and~\eqref{eq:dist abs} are sharp up to the iterated logarithm terms. When $X$ is Hilbert space we obtain a representation-theoretic proof yielding bounds corresponding to~\eqref{eq:comp abs} and~\eqref{eq:dist abs} which are sharp up to a universal constant.

preprint2009arXiv

Towards a Calculus for Non-Linear Spectral Gaps [Extended Abstract]

Given a finite regular graph G=(V,E) and a metric space (X,d_X), let $gamma_+(G,X) denote the smallest constant$ γ_+>0 $such that for all f,g:V\to X we have: \frac{1}{|V|^2}\sum_{x,y\in V} d_X(f(x),g(y))^2\le \frac{γ_+}{|E|} \sum_{xy\in E} d_X(f(x),g(y))^2. In the special case X=R this quantity coincides with the reciprocal of the absolute spectral gap of$ G$, but for other geometries the parameter γ_+(G,X), which we still think of as measuring the non-linear spectral gap of G with respect to X (even though there is no actual spectrum present here), can behave very differently. Non-linear spectral gaps arise often in the theory of metric embeddings, and in the present paper we systematically study the theory of non-linear spectral gaps, partially in order to obtain a combinatorial construction of super-expander -- a family of bounded-degree graphs G_i=(V_i,E_i), with \lim_{i\to \infty} |V_i|=\infty, which do not admit a coarse embedding into any uniformly convex normed space. In addition, the bi-Lipschitz distortion of G_i in any uniformly convex Banach space is Ω(\log |V_i|), which is the worst possible behavior due to Bourgain's embedding theorem. Such remarkable graph families were previously known to exist due to a tour de force algebraic construction of Lafforgue. Our construction is different and combinatorial, relying on the zigzag product of Reingold-Vadhan-Wigderson.

preprint2007arXiv

On metric Ramsey-type phenomena

The main question studied in this article may be viewed as a nonlinear analogue of Dvoretzky's theorem in Banach space theory or as part of Ramsey theory in combinatorics. Given a finite metric space on n points, we seek its subspace of largest cardinality which can be embedded with a given distortion in Hilbert space. We provide nearly tight upper and lower bounds on the cardinality of this subspace in terms of n and the desired distortion. Our main theorem states that for any epsilon>0, every n point metric space contains a subset of size at least n^{1-ε} which is embeddable in Hilbert space with O(\frac{\log(1/ε)}ε) distortion. The bound on the distortion is tight up to the log(1/ε) factor. We further include a comprehensive study of various other aspects of this problem.

preprint2006arXiv

Ramsey partitions and proximity data structures

This paper addresses two problems lying at the intersection of geometric analysis and theoretical computer science: The non-linear isomorphic Dvoretzky theorem and the design of good approximate distance oracles for large distortion. We introduce the notion of Ramsey partitions of a finite metric space, and show that the existence of good Ramsey partitions implies a solution to the metric Ramsey problem for large distortion (a.k.a. the non-linear version of the isomorphic Dvoretzky theorem, as introduced by Bourgain, Figiel, and Milman). We then proceed to construct optimal Ramsey partitions, and use them to show that for every e\in (0,1), any n-point metric space has a subset of size n^{1-e} which embeds into Hilbert space with distortion O(1/e). This result is best possible and improves part of the metric Ramsey theorem of Bartal, Linial, Mendel and Naor, in addition to considerably simplifying its proof. We use our new Ramsey partitions to design the best known approximate distance oracles when the distortion is large, closing a gap left open by Thorup and Zwick. Namely, we show that for any $n$ point metric space X, and k>1, there exists an O(k)-approximate distance oracle whose storage requirement is O(n^{1+1/k}), and whose query time is a universal constant. We also discuss applications of Ramsey partitions to various other geometric data structure problems, such as the design of efficient data structures for approximate ranking.

preprint2004arXiv

Markov chains in smooth Banach spaces and Gromov hyperbolic metric spaces

A metric space $X$ has {\em Markov type} 2, if for any reversible finite-state Markov chain $\{Z_t\}$ (with $Z_0$ chosen according to the stationary distribution) and any map $f$ from the state space to $X$ , the distance $D_t$ from $f(Z_0)$ to $f(Z_t)$ satisfies $\E(D_t^2) \le K^2 t \E(D_1^2)$ for some $K=K(X)<\infty$ . This notion is due to K. Ball (1992), who showed its importance for the Lipschitz extension problem. However until now, only Hilbert space (and its bi-Lipschitz equivalents) were known to have Markov type 2. We show that every Banach space with modulus of smoothness of power type 2 (in particular, $L_p$ for $p>2$ ) has Markov type 2; this proves a conjecture of Ball. We also show that trees, hyperbolic groups and simply connected Riemannian manifolds of pinched negative curvature have Markov type 2. Our results are applied to settle several conjectures on Lipschitz extensions and embeddings. In particular, we answer a question posed by Johnson and Lindenstrauss in 1982, by showing that for $1<q<2<p<\infty$ , any Lipschitz mapping from a subset of $L_p$ to $L_q$ has a Lipschitz extension defined on all of $L_p$ .

Assaf Naor

Research overview

Is this your work?

47 publications

An integer parallelotope with small surface area

Cayley graphs that have a quantum ergodic eigenbasis

Efficient Rounding for the Noncommutative Grothendieck Inequality

A spectral gap precludes low-dimensional embeddings

Discrete Riesz transforms and sharp metric XpX_pXp​ inequalities

Heat flow and quantitative differentiation

Restricted invertibility revisited

Bourgain's discretization theorem

Metric Xp{X}_pXp​ inequalities

On Lipschitz extension from finite subsets

Pythagorean powers of hypercubes

Snowflake universality of Wasserstein spaces

Uniform nonextendability from nets

Expanders with respect to Hadamard spaces and random graphs

Solution of the propeller conjecture in R3\mathbb{R}^3R3

A doubling subset of LpL_pLp​ for p>2p>2p>2 that is inherently infinite dimensional

Comparison of metric spectral gaps

Nonlinear spectral calculus and super-expanders

Pisier's inequality revisited

Spectral calculus and Lipschitz extension for barycentric metric spaces

An introduction to the Ribe program

Discretization and affine approximation in high dimensions

Krivine schemes are optimal

Locally decodable codes and the failure of cotype for projective tensor products

Ultrametric subsets with large Hausdorff dimension

Vertical versus horizontal Poincaré inequalities on the Heisenberg group

A note on dichotomies for metric transforms

Grothendieck-type inequalities in combinatorial optimization

Metric Cotype

Sparse quadratic forms and their geometric applications (after Batson, Spielman and Srivastava)

The Grothendieck constant is strictly smaller than Krivine's bound

Ultrametric skeletons

Absolutely minimal Lipschitz extension of tree-valued mappings

Assouad's theorem with dimension independent of the snowflaking

Improved bounds in the metric cotype inequality for Banach spaces

Improved bounds in the scaled Enflo type inequality for Banach spaces

L_1 embeddings of the Heisenberg group and fast estimation of graph isoperimetry

Markov convexity and local rigidity of distorted metrics

Maximum gradient embeddings and monotone clustering

On the Banach space valued Azuma inequality and small set isoperimetry of Alon-Roichman graphs

Overlap properties of geometric expanders

Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem

Sharp quantitative nonembeddability of the Heisenberg group into superreflexive Banach spaces

Towards a Calculus for Non-Linear Spectral Gaps [Extended Abstract]

On metric Ramsey-type phenomena

Ramsey partitions and proximity data structures

Markov chains in smooth Banach spaces and Gromov hyperbolic metric spaces

See the researcher in context

Building this map preview

Discrete Riesz transforms and sharp metric $X_p$ inequalities

Metric ${X}_p$ inequalities

Solution of the propeller conjecture in $\mathbb{R}^3$

A doubling subset of $L_p$ for $p>2$ that is inherently infinite dimensional