The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite (2009)
William B. Johnson, Assaf Naor
Let X be a normed space that satisfies the Johnson-Lindenstrauss lemma (J-L lemma, in short) in the sense that for any integer n and any x1,..., xn ∈ X there exists a linear mapping L: X → F,...
A $(\log n)^{\Omega(1)}$ integrality gap for the Sparsest Cut SDP (2009)
Cheeger, Jeff, Kleiner, Bruce, Naor, Assaf
We show that the Goemans-Linial semidefinite relaxation of the Sparsest Cut problem with general demands has integrality gap $(\log n)^{\Omega(1)}$. This is achieved by exhibiting $n$-point metric...
Compression bounds for Lipschitz maps from the Heisenberg group to $L_1$ (2009)
Cheeger, Jeff, Kleiner, Bruce, Naor, Assaf
We prove a quantitative bi-Lipschitz nonembedding theorem for the Heisenberg group with its Carnot-Carath\'eodory metric and apply it to give a lower bound on the integrality gap of the...
Towards a Calculus for Non-Linear Spectral Gaps [Extended Abstract] (2009)
Given a finite regular graph G=(V,E) and a metric space (X,d_X), let $gamma_+(G,X) denote the smallest constant $\gamma_+>0$ such that for all f,g:V\to X we have: \frac{1}{|V|^2}\sum_{x,y\in V}...
Sharp kernel clustering algorithms and their associated Grothendieck inequalities (2009)
In the kernel clustering problem we are given a (large) $n\times n$ symmetric positive semidefinite matrix $A=(a_{ij})$ with $\sum_{i=1}^n\sum_{j=1}^n a_{ij}=0$ and a (small) $k\times k$ symmetric...
$L_p$ compression, traveling salesmen, and stable walks (2009)
We show that if $H$ is a group of polynomial growth whose growth rate is at least quadratic then the $L_p$ compression of the wreath product $\Z\bwr H$ equals $\max{\frac{1}{p},{1/2}}$. We also show...
Optp (A) ≔ max ai jxixj: (x1,..., xn) ∈ R (2009)
Guy Kindler, Assaf Naor, Gideon Schechtman
For p ≥ 2 we consider the problem of, given an n × n matrix A = (ai j) whose diagonal entries vanish, approximating in polynomial time the number n�
Guy Kindler, Assaf Naor, Gideon Schechtman
hardness threshold of the ℓp Grothendieck problem
Boolean functions whose Fourier transform is concentrated on the first two levels (2008)
Ehud Friedgut, Gil Kalai, Assaf Naor
x2;:::; xn) whose Fourier coefficients are concentrated on the lowest two levels. We show that such a function is close to a constant function or to a function of the form f = xk or f = 1 \Gamma xk....
Approximate kernel clustering (2008)
In the kernel clustering problem we are given a large $n\times n$ positive semi-definite matrix $A=(a_{ij})$ with $\sum_{i,j=1}^na_{ij}=0$ and a small $k\times k$ positive semi-definite matrix...
The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite (2008)
Johnson, William B., Naor, Assaf
Let $X$ be a normed space that satisfies the Johnson-Lindenstrauss lemma (J-L lemma, in short) in the sense that for any integer $n$ and any $x_1,\ldots,x_n\in X$ there exists a linear mapping...
We introduce the notion of the scaled Enflo type of a metric space, and show that for Banach spaces, scaled Enflo type p is equivalent to Rademacher type p. 1.
CSE 254 Handout Nearest Neighbor Preserving Embeddings 1 Nearest Neighbor Search (2008)
Paper Piotr Indyk, Assaf Naor, Konstantin Pervyshev
Problem 1 (The nearest neighbor problem). Given a set X ⊂ R n, build a data structure which given any query x ∈ R n, quickly reports the point x ′ in X that is (approximately) closest to x....
In this paper we introduce the notion of nearest neighbor preserving embeddings. These are randomized embeddings between two metric spaces which preserve the (approximate) nearest neighbors. We give...
Various new nonembeddability results (mainly into L1) are proved via Fourier analysis. In particular, it is shown that the Edit Distance on {0, 1} d has L1 distortion Ω ( � log d / log log d). We...
Markov Convexity and Local Rigidity of Distorted Metrics (2008)
The geometry of discrete tree metrics is studied from the following perspectives: 1. Markov p-convexity, which was shown by Lee, Naor, and Peres to be a property of p-convex Banach space, is shown...
Embeddings of Discrete Groups and the Speed of Random Walks (2008)
Let G be a group generated by a finite set S and equipped with the associated left-invariant word metric dG. For a Banach space X, let α*X(G) (respectively, α/#X(G)) be the supremum over all α ≥...
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
In this note, we consider the metric Ramsey problem for the normed spaces # p. Namely, given some 1
Yair Bartal, Nathan Linial, Assaf Naor
The main question studied in this article may be viewed as a non-linear analog of Dvoretzky's Theorem in Banach space theory or as part of Ramsey Theory in combinatorics. Given a nite metric...
James R. Lee, Assaf Naor, An Immediate
We show that any embedding of the level k diamond graph of Newman and Rabinovich [4] into L p, 1
Yair Bartal, Nathan Linial, Assaf Naor
The main question studied in this article may be viewed as a non-linear analog of Dvoretzky's Theorem in Banach space theory or as part of Ramsey Theory in combinatorics. Given a nite metric...
We study the metric properties of finite subsets of L1. The analysis of such metrics is central to a number of important algorithmic problems involving the cut structure of weighted graphs, including...
Embeddings of discrete groups and the speed of random walks (2007)
For a finitely generated group G and a banach space X let \alpha^*_X(G) (respectively \alpha^#_X(G)) be the supremum over all \alpha\ge 0 such that there exists a Lipschitz mapping (respectively an...
The wreath product of Z with Z has Hilbert compression exponent 2/3 (2007)
Austin, Tim, Naor, Assaf, Peres, Yuval
Let G be a finitely generated group, equipped with the word metric d associated with some finite set of generators. The Hilbert compression exponent of G is the supremum over all $\alpha\ge 0$ such...
The two possible values of the chromatic number of a random graph (2007)
Achlioptas, Dimitris, Naor, Assaf
Given d \in (0,infty) let k_d be the smallest integer k such that d < 2k\log k. We prove that the chromatic number of a random graph G(n,d/n) is either k_d or k_d+1 almost surely.
Scaled Enflo type is equivalent to Rademacher type (2007)
We introduce the notion of the scaled Enflo type of a metric space, and show that for Banach spaces, scaled Enflo type p is equivalent to Rademacher type p.
Trees and Markov convexity (2007)
Lee, James R., Naor, Assaf, Peres, Yuval
We show that an infinite weighted tree admits a bi-Lipschitz embedding into Hilbert space if and only if it does not contain arbitrarily large complete binary trees with uniformly bounded distortion....
The Euclidean distortion of the lamplighter group (2007)
Austin, Tim, Naor, Assaf, Valette, Alain
We show that the cyclic lamplighter group $C_2 \bwr C_n$ embeds into Hilbert space with distortion ${\rm O}(\sqrt{\log n})$. This matches the lower bound proved by Lee, Naor and Peres in...
Annals of Mathematics, 162 (2005), 643–710 On metric Ramsey-type phenomena (2007)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
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...
An application of metric cotype to quasisymmetric embeddings (2006)
We apply the notion of metric cotype to show that $L_p$ admits a quasisymmetric embedding into $L_q$ if and only if $p\le q$ or $q\le p\le 2$.
Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces (2006)
Naor, Assaf, Peres, Yuval, Schramm, Oded, Sheffield, Scott
A metric space $X$ has 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...
Maximum gradient embeddings and monotone clustering (2006)
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...
Planar earthmover is not in l1 (2006)
We show that any L1 embedding of the transportation cost (a.k.a. Earthmover) metric on probability measures supported on the grid {0, 1,..., n} 2 ⊆ R 2 incurs distortion Ω � � log n �. We...
Ramsey partitions and proximity data structures (2005)
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...
The two possible values of the chromatic number of a random graph (2005)
Achlioptas, Dimitris, Naor, Assaf
Given $d \in (0,\infty)$ let $k_d$ be the smallest integer $k$ such that $d
Lower bounds on Locality Sensitive Hashing (2005)
Motwani, Rajeev, Naor, Assaf, Panigrahy, Rina
Given a metric space $(X,d_X)$, $c\ge 1$, $r>0$, and $p,q\in [0,1]$, a distribution over mappings $\h:X\to \mathbb N$ is called a $(r,cr,p,q)$-sensitive hash family if any two points in $X$ at...
Nonembeddability theorems via Fourier analysis (2005)
Various new nonembeddability results (mainly into $L_1$) are proved via Fourier analysis. In particular, it is shown that the Edit Distance on $\{0,1\}^d$ has $L_1$ distortion $(\log...
Planar Earthmover is not in $L_1$ (2005)
Naor, Assaf, Schechtman, Gideon
We show that any $L_1$ embedding of the transportation cost (a.k.a. Earthmover) metric on probability measures supported on the grid $\{0,1,...,n\}^2\subseteq \R^2$ incurs distortion...
On metric Ramsey-type phenomena (2005)
Bartal, Yair, Linial, Nathan, Mendel, Manor, Naor, Assaf
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...
Euclidean distortion and the Sparsest Cut (2005)
Arora, Sanjeev, Lee, James R., Naor, Assaf
We prove that every $n$-point metric space of negative type (and, in particular, every $n$-point subset of $L_1$) embeds into a Euclidean space with distortion $O(\sqrt{\log n} \cdot\log \log n)$, a...
Scaled Enflo type is equivalent to Rademacher type (2005)
We introduce the notion of scaled Enflo type of a metric space, and show that for Banach spaces, scaled Enflo type p is equivalent to Rademacher type p.
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,...
A probabilistic approach to the geometry of the \ell_p^n-ball (2005)
Barthe, Franck, Guedon, Olivier, Mendelson, Shahar, Naor, Assaf
This article investigates, by probabilistic methods, various geometric questions on B_p^n, the unit ball of \ell_p^n. We propose realizations in terms of independent random variables of several...
A probabilistic approach to the geometry of the ℓpn-ball (2005)
Barthe, Franck, Guédon, Olivier, Mendelson, Shahar, Naor, Assaf
This article investigates, by probabilistic methods, various geometric questions on Bpn, the unit ball of ℓpn. We propose realizations in terms of independent random variables of several...
On metric Ramsey-type phenomena (2005)
Mendel, Manor, Naor, Assaf, Linial, Nathan, Bartal, Yair
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...
The two possible values of the chromatic number of a random graph (2005)
Achlioptas, Dimitris, Naor, Assaf
Given d ¿¿ (0,¿¿) let kd be the smallest integer k such that d < 2k log k. We prove that the chromatic number of a random graph G(n, d/n) is either kd or kd + 1 almost surely.
Euclidean distortion and the Sparsest Cut (2005)
Sanjeev Arora, James R. Lee, Assaf Naor
Bi-Lipschitz embeddings of finite metric spaces, a topic originally studied in geometric analysis and Banach space theory, became an integral part of theoretical computer science following work of...
Euclidean distortion and the Sparsest Cut (2005)
Sanjeev Arora, James R. Lee, Assaf Naor
We prove that every n-point metric space of negative type (and, in particular, every npoint subset of L1) embeds into a Euclidean space with distortion O ( √ log n · log log n), a result which is...
A probabilistic approach to the geometry of the ℓ n p ball, Annals of Probability (2005)
Franck Barthe, Olivier Guédon, Shahar Mendelson, Assaf Naor
This article investigates, by probabilistic methods, various geometric questions on. We propose realizations in terms of independent random vari-Bn p, the unit ball of ℓnp ables of several...
Quadratic forms on graphs (2005)
Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor
We introduce a new graph parameter, called the Grothendieck constant of a graph G = (V, E), which is defined as the least constant K such that for every A: E → R,
Quadratic forms on graphs (2005)
Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor
We introduce a new graph parameter, called the Grothendieck constant of a graph G = (V, E), which is defined as the least constant K such that for every A: E → R,
A probabilistic approach to the geometry of the ℓ n p ball, Annals of Probability (2005)
Franck Barthe, Olivier Guédon, Shahar Mendelson, Assaf Naor
This article investigates, by probabilistic methods, various geometric questions on B n p, the unit ball of ℓ n p. We propose realizations in terms of independent random variables of several...
Quadratic forms on graphs (2005)
Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor
We introduce a new graph parameter, called the Grothendieck constant of a graph G = (V, E), which is defined as the least constant K such that for every A: E → R,
Measured descent: A new embedding method for finite metrics (2004)
Krauthgamer, Robert, Lee, James R., Mendel, Manor, Naor, Assaf
We devise a new embedding technique, which we call measured descent, based on decomposing a metric space locally, at varying speeds, according to the density of some probability measure. This...
Markov chains in smooth Banach spaces and Gromov hyperbolic metric spaces (2004)
Naor, Assaf, Peres, Yuval, Schramm, Oded, Sheffield, Scott
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...
Metric structures in L_1: Dimension, snowflakes, and average distortion (2004)
Lee, James R., Mendel, Manor, Naor, Assaf
We study the metric properties of finite subsets of L_1. The analysis of such metrics is central to a number of important algorithmic problems involving the cut structure of weighted graphs,...
Limitations to Frechet's Metric Embedding Method (2004)
Batal, Yair, Linial, Nathan, Mendel, Manor, Naor, Assaf
Frechet's classical isometric embedding argument has evolved to become a major tool in the study of metric spaces. An important example of a Frechet embedding is Bourgain's embedding. The authors...
On Metric Ramsey-type Dichotomies (2004)
Bartal, Yair, Linial, Nathan, Mendel, Manor, Naor, Assaf
The classical Ramsey theorem, states that every graph contains either a large clique or a large independent set. Here we investigate similar dichotomic phenomena in the context of finite metric...
Euclidean quotients of finite metric spaces (2004)
This paper is devoted to the study of quotients of finite metric spaces. The basic type of question we ask is: Given a finite metric space M, what is the largest quotient of (a subset of) M which...
On metric Ramsey-type phenomena (2004)
Bartal, Yair, Linial, Nathan, Mendel, Manor, Naor, Assaf
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 some low distortion metric Ramsey problems (2004)
Bartal, Yair, Mendel, Nathan Linial. Manor, Naor, Assaf
In this note, we consider the metric Ramsey problem for the normed spaces l_p. Namely, given some 12 we are unable to determine the answer, but estimates are provided for the possible location of...
Solution of Shannon’s problem on the monotonicity of entropy (2004)
Shiri Artstein, Keith M. Ball, Franck Barthe, Assaf Naor
The entropy of a real valued random variable X with density f: R → [0, ∞) is defined as
The two possible values of the chromatic number of a random graph (2004)
Dimitris Achlioptas, Assaf Naor
Abstract Given d 2 (0, 1) let kd be the smallest integer k such that d < 2k log k. We prove that thechromatic number of a random graph G(n, d/n) is either kd or kd + 1 almost surely. 1...
Measured descent: A new embedding method for finite metrics (2004)
Robert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor
We devise a new embedding technique, which we call measured descent, based on decomposing a metric space locally, at varying speeds, according to the density of some probability measure.
Measured descent: A new embedding method for finite metrics (2004)
Robert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor
We devise a new embedding technique, which we call measured descent, based on decomposing a metric space locally, at varying speeds, according to the density of some probability measure. This...
Measured descent: A new embedding method for finite metrics (2004)
Robert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor
We devise a new embedding technique, which we call measured descent, based on decomposing a metric space locally, at varying speeds, according to the density of some probability measure. This...
Approximating the cut-norm via Grothendieck’s inequality (2004)
The cut-norm ||A||C of a real matrix A = (aij)i∈R,j∈S is the maximum, over all I ⊂ R, J ⊂ S of the quantity | � i∈I,j∈J aij|. This concept plays a major role in the design of efficient...
Entropy jumps in the presence of a spectral gap (2003)
Ball, Keith, Barthe, Franck, Naor, Assaf
It is shown that if X is a random variable whose density satisfies a Poincaré inequality, and Y is an independent copy of X, then the entropy of (X + Y)/√2 is greater than that of X by a fixed...
On the Maximum Satisfiability of Random Formulas (2003)
Achlioptas, Dimitris, Naor, Assaf, Peres, Yuval
Maximum satisfiability is a canonical NP-hard optimization problem that appears empirically hard for random instances. Let us say that a Conjunctive normal form (CNF) formula consisting of...
Limitations to Fréchet metric embedding method (2003)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
Abstract Fr'echet's classical isometric embedding argument has evolved to become a major toolin the study of metric spaces. An important example of a Fr'echet embedding is...
Entropy jumps in the presence of a spectral gap (2003)
Keith Ball, Franck Barthe, Assaf Naor
Abstract It is shown that if X is a random variable whose density satisfies a Poincar'e inequality, and Y is an independent copy of X, then the entropy of (X + Y)/p2 is greater than that of X by...
On metric Ramsey-type phenomena (2003)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
The main question studied in this article may be viewed as a non-linear analogue of Dvoretzky’s Theorem in Banach space theory or as part of Ramsey Theory in combinatorics. Given a finite metric...
On the Fraction of Satisfiable Clauses in Typical Formulas (2003)
Dimitris Achlioptas, Assaf Naor, Yuval Peres
Given n Boolean variables x1,..., xn, a k-clause is a disjunction of k literals, where a literal is a variable or its negation. A k-CNF formula is a conjunction of a finite number of k-clauses. Call...
Euclidean Quotients of Finite Metric Spaces (2003)
Manor Mendel School, Manor Mendel, Assaf Naor
This paper is devoted to the study of quotients of finite metric spaces. The basic type of question we ask is: Given a finite metric space M and # 1, what is the largest quotient of (a subset of) M...
Extending Lipschitz functions via random metric partitions (2003)
James Lee Berkeley, James R. Lee, Assaf Naor
this paper to the higher order Whitney extension problem
On metric Ramsey-type phenomena (2003)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
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...
On the maximum satisfiability of random formulas (2003)
Dimitris Achlioptas, Assaf Naor, Yuval Peres
Say that a k-CNF a formula is p-satisfiable if there exists a truth assignment satisfying a fraction 1 − 2 −k + p2 −k of its clauses (note that every k-CNF formula is 0-satisfiable). Let Fk(n,...
Limitations to Fréchet's Metric Embedding Method (2003)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
Frechet's classical isometric embedding argument has evolved to become a major tool in the study of metric spaces. An important example of a Frechet embedding is Bourgain's embedding [4]....
On Metric Ramsey-type Dichotomies (2002)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
The classical Ramsey theorem, states that every graph contains either a large clique or a large independent set. Here we investigate similar dichotomic phenomena in the context of finite metric...
On Metric Ramsey-type Dichotomies (2002)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
The classical Ramsey theorem, states that every graph contains either a large clique or a large independent set. Here we investigate similar dichotomic phenomena in the context of finite metric...
Girth and Euclidean distortion (2002)
Nathan Linial, Avner Magen, Assaf Naor
Let G be a k-regular graph, k 3, with girth g. We prove that every embedding f: G! `2 has distortion
Girth and Euclidean distortion (2002)
Nathan Linial, Avner Magen, Assaf Naor
Let G be a k-regular graph, k 3, with girth g. We prove that every embedding f: G! `2 has distortion
Remarks on Non Linear Type and Pisier's Inequality (2002)
We prove that for the class of UMD Banach spaces, the log n term in Pisier's inequality [17] can be replaced by a constant independent of n. This is applied to show that for UMD Banach spaces,...
Abstract Let G be a k-regular graph, k * 3, with girth g. We prove that every embedding f: G! `2 has distortion \Omega ( p g). Two proofs are given, one based on Markov Type [1] and the other on...
Boolean Functions whose Fourier Transform is Concentrated on the First Two Levels (2001)
Ehud Friedgut, Gil Kalai, Assaf Naor
In this note we describe Boolean functions f(x 1 ; x 2 ; : : : ; xn ) whose Fourier coecients are concentrated on the lowest two levels. We show that such a function is close to a constant function...
We show that any embedding of the level k diamond graph of Newman and Rabinovich [6] into Lp, 1 < p ≤ 2, requires distortion at least � k(p − 1) + 1. An immediate corollary is that there...
The Two Possible Values of the Chromatic Number of a Random Graph
Dimitris Achlioptas, Assaf Naor
Given d let k d be the smallest integer k such that d < 2k log k. We prove that the chromatic number of a random graph G(n, d/n) is either k d or k d + 1 almost surely. 1