Assaf Naor
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
Research Subjects
Assaf Naor has a total of 7 co-authors. Here are the top co-authors by number of shared publications:
- Manor Mendel
The Open University of Israel, Raanana, Israel
2 shared publications - Alan Chang
Washington University in St. Louis, St. Louis, USA
1 shared publication - Kevin Ren
Princeton University, Princeton, USA
1 shared publication Ofer Neiman
Ben Gurion University of the Negev, Beer Sheva, Israel
1 shared publicationRomain Tessera
Université Paris-Sud, Orsay, France
1 shared publicationTim Austin
New York University, USA
1 shared publication
Latest Publications
- Open Access
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 643-652
Optimal Rounding for Sparsest Cut
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 643-652
Open AccessOptimal Rounding for Sparsest Cut
- Open Access
- 31 March 2024
- Published by European Mathematical Society - EMS - Publishing House GmbH
Extension, Separation and Isomorphic Reverse Isoperimetry
Extension, Separation and Isomorphic Reverse Isoperimetry, by Assaf Naor. Published by EMS Press
- 31 March 2024
- Published by European Mathematical Society - EMS - Publishing House GmbH
Open AccessExtension, Separation and Isomorphic Reverse Isoperimetry
Extension, Separation and Isomorphic Reverse Isoperimetry, by Assaf Naor. Published by EMS Press
- 19 July 2019
- Published by European Mathematical Society - EMS - Publishing House GmbH in Journal of the European Mathematical Society
- Vol. 21 (11) , 3415-3466
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 \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.
- 19 July 2019
- Published by European Mathematical Society - EMS - Publishing House GmbH in Journal of the European Mathematical Society
- Vol. 21 (11) , 3415-3466
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 \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.
- 27 August 2013
- Published by European Mathematical Society - EMS - Publishing House GmbH in Groups, Geometry, and Dynamics
- Vol. 7 (3) , 497-522
Sharp quantitative nonembeddability of the Heisenberg group into superreflexive Banach spaces
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.
- 27 August 2013
- Published by European Mathematical Society - EMS - Publishing House GmbH in Groups, Geometry, and Dynamics
- Vol. 7 (3) , 497-522
Sharp quantitative nonembeddability of the Heisenberg group into superreflexive Banach spaces
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
- 24 November 2012
- Published by European Mathematical Society - EMS - Publishing House GmbH in Journal of the European Mathematical Society
- Vol. 15 (1) , 287-337
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.
- 24 November 2012
- Published by European Mathematical Society - EMS - Publishing House GmbH in Journal of the European Mathematical Society
- Vol. 15 (1) , 287-337
Open AccessMarkov 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.
- Open Access
- 14 October 2012
- Published by European Mathematical Society - EMS - Publishing House GmbH in Revista Matemática Iberoamericana
- Vol. 28 (4) , 1123-1142
Assouad’s theorem with dimension independent of the snowflaking
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 .
- 14 October 2012
- Published by European Mathematical Society - EMS - Publishing House GmbH in Revista Matemática Iberoamericana
- Vol. 28 (4) , 1123-1142
Open AccessAssouad’s theorem with dimension independent of the snowflaking
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
- 30 June 2007
- Published by European Mathematical Society - EMS - Publishing House GmbH in Journal of the European Mathematical Society
- Vol. 9 (2) , 253-275
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 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.
- 30 June 2007
- Published by European Mathematical Society - EMS - Publishing House GmbH in Journal of the European Mathematical Society
- Vol. 9 (2) , 253-275
Open AccessRamsey 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 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.