ANAssaf Naor

Assaf Naor

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Assaf Naor has a total of 7 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Optimal Rounding for Sparsest Cut

    by Alan Chang, Assaf Naor, Kevin Ren

  • Open Access

    Extension, Separation and Isomorphic Reverse Isoperimetry

    by Assaf Naor

    Extension, Separation and Isomorphic Reverse Isoperimetry, by Assaf Naor. Published by EMS Press


  • Heat flow and quantitative differentiation

    by Tuomas Hytönen, Assaf Naor

    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 \Lambda:X\to Y such that \|f(y)-\Lambda(y)\|_Y\le \varepsilon r for every y\in x+rB_X . This is an improved bound for a fundamental quantitative differentiation problem that was formulated by Bates, Johnson, Lindenstrauss, Preiss and Schechtman (1999), and consequently it yields a new proof of Bourgain's discretization theorem (1987) for uniformly convex targets. The strategy of our proof is inspired by Bourgain's original approach to the discretization problem, which takes the affine mapping \Lambda to be the first order Taylor polynomial of a time- t Poisson evolute of an extension of f to all of X and argues that, under appropriate assumptions on f , there must exist a time t\in (0,\infty) at which \Lambda is (quantitatively) invertible. However, in the present context we desire a more stringent conclusion, namely that \Lambda well-approximates f on a macroscopically large ball, in which case we show that for our argument to work one cannot use the Poisson semigroup. Nevertheless, our strategy does succeed with the Poisson semigroup replaced by the heat semigroup. As a crucial step of our proof, we establish a new uniformly convex-valued Littlewood–Paley–Stein \mathcal{G} -function inequality for the heat semigroup; influential work of Martínez, Torrea and Xu (2006) obtained such an inequality for subordinated Poisson semigroups but left the important case of the heat semigroup open. As a byproduct, our proof also yields a new and simple approach to the classical Dorronsoro theorem (1985) even for real-valued functions.


  • Sharp quantitative nonembeddability of the Heisenberg group into superreflexive Banach spaces

    by Tim Austin, Assaf Naor, Romain Tessera

    Let \mathbb 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\colon \mathbb H\to X there exist x,y\in \mathbb H with d_W(x,y) arbitrarily large and \frac{\|f(x)-f(y)\|}{d_W(x,y)}\lesssim \bigg(\frac{\log\log d_W(x,y)}{\log d_W(x,y)}\bigg)^{1/p}. \qquad (1) We also show that any embedding into X of a ball of radius R\ge 4 in \mathbb H incurs bi-Lipschitz distortion that grows at least as a constant multiple of \left(\frac{\log R}{\log\log R}\right)^{1/p}. \qquad (2) Both (1) and (2) are sharp up to the iterated logarithm terms. When X is Hilbert space we obtain a representation-theoretic proof yielding bounds corresponding to (1) and (2) which are sharp up to a universal constant.


  • Open Access

    Markov convexity and local rigidity of distorted metrics

    by Manor Mendel, Assaf Naor

    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.


  • Open Access

    Assouad’s theorem with dimension independent of the snowflaking

    by Assaf Naor, Ofer Neiman

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


  • Open Access

    Ramsey partitions and proximity data structures

    by Manor Mendel, Assaf Naor

    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 in [8]). We then proceed to construct optimal Ramsey partitions, and use them to show that for every \varepsilon \in (0,1) , every n -point metric space has a subset of size n^{1-\varepsilon} which embeds into Hilbert space with distortion O(1/\varepsilon) . This result is best possible and improves part of the metric Ramsey theorem of Bartal, Linial, Mendel and Naor [5], in addition to considerably simplifying its proof. We use our new Ramsey partitions to design approximate distance oracles with a universal constant query time, closing a gap left open by Thorup and Zwick in [32]. Namely, we show that for every n point metric space X , and k\geq 1 , there exists an O(k) -approximate distance oracle whose storage requirement is O\left( n^{1+1/k}\right) , 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.