BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Assaf Naor appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
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$.
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.
$ \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.
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.
$ \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}\}$.
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$.
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.
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}$.
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.
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.
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.
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.
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.
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.
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}$.
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$.
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.
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.
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.
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.
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.
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.
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$.
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.
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.
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$.
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.
We survey connections of the Grothendieck inequality and its variants to combinatorial optimization and computational complexity.
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.
We survey the work of Batson, Spielman and Srivastava on graph sparsification, and we describe some of its recently discovered geometric applications.
We prove that $K_G<\fracπ{2\log(1+\sqrt{2})}$, where $K_G$ is the Grothendieck constant.
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.
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.
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$.
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)}.
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].
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$.
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.
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.
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.
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$.
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.
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.
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.
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.
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.
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$.