Home page of Assaf Naor

Assaf Naor

Courant Institute of Mathematical Sciences
New York University
Departments of mathematics and computer science

My CV: ps dvi pdf.

Research Interests.

Analysis.
Probability.
Quantitative geometry.
Applications of the above to combinatorics, mathematical physics and theoretical computer science.

Professional Activities.

The Center for Computational Intractability (CCI), which is funded by an NSF Expeditions in Computing award.
The Courant mathematics colloquium.
The Courant theory of computing seminar.
Scientific Advisory Board of the Institute for Pure and Applied Mathematics (IPAM).
Editorial:
- International Mathematics Research Notices.
- Journal of the American Mathematical Society (JAMS).
- Journal of Topology and Analysis.
- Mathematika.
- Probability Theory and Related Fields.
- Theory of Computing.
- Proceedings of the National Academy of Sciences: guest editor of the Special Feature on Quantitative Geometry.
- Israel Journal of Mathematics: guest editor of the special volume in the memory of Joram Lindenstrauss.
- Program committee of STOC 2006, SODA 2007, STOC 2010.
Conference organization:
- Metric Geometry and Geometric Embeddings of Discrete Metric Spaces at Texas A&M University, July 17-22, 2006.
- Applications of the Arora-Rao-Vazirani Algorithm, special session at INFORMS 2006.
- Geometry and Algorithms at the International Centre for Mathematical Sciences in Edinburgh, April 16-21, 2007.
- Algorithmic Convex Geometry at the American Institute of Mathematics in Palo Alto, November 5-9, 2007.
- Geometry in the Design of Algorithms at Princeton University, October 29-31, 2008.
- Quantitative and Computational Aspects of Metric Geometry at the Institute for Pure and Applied Mathematics (IPAM) in Los Angeles, January 12-16, 2009.
- Probability in Asymptotic Geometry at Texas A&M University, July 20-24, 2009.
Research semesters:
- Discrete Analysis at the Isaac Newton Institute for Mathematical Sciences in Cambridge, winter 2011. Conference organization within this semester:
  - Embeddings, January 10-14, 2011.
- Quantitative Geometry at the Mathematical Sciences Research Institute (MSRI) in Berkeley, fall 2011. Conference organization within this semester:
  - Connections for Women in Quantitative Geometry, August 18-19, 2011.
  - Introductory Workshop on Quantitative Geometry, August 22-26, 2011.
  - Probabilistic Reasoning in Quantitative Geometry, September 19-23, 2011.
  - Embedding Problems in Banach Spaces and Group Theory, October 17-21, 2011.
  - Quantitative Geometry in Computer Science, December 5-9, 2011.

Teaching.

Fall 2007: The local theory of Banach spaces.
Spring 2008: The local theory of metric spaces and its algorithmic applications.
Fall 2008: Algebra 1, and a topics course on concentration of measure. Scribe notes by Lingjiong Zhu.
Fall 2009: Algebra 1.
Fall 2010: Topics in the local theory of Banach spaces. Scribe notes by Evan Chou.
Spring 2011: Analysis 1.
Spring 2012: Algebra 1 and a topics course on geometric embeddings of discrete spaces.
Fall 2013: Algebra 1.

See http://math.nyu.edu/courses/ for more information on the mathematics courses being offered at the Courant Institute, and see http://www.cs.nyu.edu/web/Academic/Courses/ for more information on the computer science courses being offered at the Courant Institute.

Advising.

Ph.D. students:
- Ohad Giladi (Courant Institute, 2007-2011).
- Steven Heilman (Courant Institute, 2009-).
- Sean Li (Courant Institute, 2008-2013).
M.Sc. students:
- Hassane Kone (Courant Institute, 2009-2010).
Undergraduate research advisees:
- Aukosh Jagannath (Courant Institute, 2010-2011. Funded by REU supplement to NSF Expeditions in Computing award).
Post-doctoral advisees:
- Alexandr Andoni ( CCI postdoc, affiliated with Courant, funded by NSF Expeditions in Computing award, 2009-2010).
- Per Austrin (Courant Computer Science Department, funded by NSF Expeditions in Computing award, 2009-2010).
- Jop Briët (Courant Institute, 2013-2015. Funded by Netherlands Rubicon grant).
- Daniel Dadush (Simons postdoc in computer science, Courant Institute, 2012-2014).
- Arie Israel (Courant Institute, 2011-2014. Funded by NSF postdoctoral fellowship).
- Ofer Neiman (Courant Instructor, partially funded by NSF Expeditions in Computing award, 2009-2010).
- Grigoris Paouris (Courant Instructor, 2007-2008).
I also advised the following students as interns at Microsoft Research:
- Nir Avni (2005).
- James R. Lee (2003-2004).
- Konstantin Makarychev (2005).
- Yury Makarychev (2005-2006).
- Lior Silberman (2004).

Publications and Preprints.

Geometric Problems in Non-Linear Functional Analysis. M.Sc. Thesis, Hebrew University (1998). Thesis advisor: Joram Lindenstrauss.
Linear and Non-Linear Geometric Problems in Banach Spaces. Ph.D. Thesis, Hebrew University (2002). Thesis advisor: Joram Lindenstrauss. The introduction to the thesis: ps dvi pdf.
Isomorphic Embedding of l_p^n, 1<p<2, into l_1^{(1+\epsilon) n} (with A. Zvavitch), Israel Journal of Mathematics 122 (2001), 371-380. ps dvi pdf.
A Phase Transition Phenomenon Between the Isometric and Isomorphic Extension Problems for Holder Functions Between L_p Spaces, Mathematika 48 (2001), 253-271. ps dvi pdf.
Projecting the Surface Measure of the Sphere of l_p^n (with D. Romik), Annales de l'Institut Henri Poincare' (B), Probability and Statistics 39 (2003), 241-261. ps dvi pdf.
The Surface Measure and Cone Measure on the Sphere of l_p^n, Transactions of the American Mathematical Society 359 (2007), 1045-1079. ps dvi pdf.
Lipschitz Sums of Convex Functions (with M. Csornyei), Studia Mathematica 158 (2003), 269-286. ps dvi pdf.
Hyperplane Projections of the Unit Ball of l_p^n (with F. Barthe), Discrete and Computational Geometry 27 (2002), no. 2, 215- 226. ps dvi pdf.
A Note on Simultaneous Polar and Cartesian Decomposition, (with F. Barthe and M. Csornyei), Geometric Aspects of Functional Analysis, Springer Lecture Notes in Mathematics 1807, 1-19. ps dvi pdf.
Girth and Euclidean Distortion (with N. Linial and A. Magen), Geometric and Functional Analysis (GAFA)12 (2002), no. 2, 380-394. ps dvi pdf . The following conference version has appeared in STOC 2002.
Remarks on Non Linear type and Pisier's Inequality (with G. Schechtman), Journal für die reine und angewandte Mathematik (Crelle's Journal) 552 (2002) 213-236. ps dvi pdf.
Boolean Functions whose Fourier Transform is Concentrated on the First Two Levels (with E. Friedgut and G. Kalai), Advances in Applied Mathematics 29, no. 3, (2002) 427-437. ps dvi pdf.
Entropy Jumps in the Presence of a Spectral Gap (with K. Ball and F. Barthe), Duke Mathematical Journal 119, No. 1, 41-63 (2003). ps dvi pdf.
On Metric Ramsey Type Phenomena (with Y. Bartal, N. Linial and M. Mendel), Annals of Mathematics 162(2), 643-709 (2005). ps dvi pdf. The following conference version has appeared in STOC 2003.
Solution of Shannon's Problem on the Monotonicity of Entropy (with K. Ball, F. Barthe and S. Artstein), Journal of the American Mathematical Society 17, 975-982 (2004). ps dvi pdf.
On the Rate of Convergence in the Entropic Central Limit Theorem (with K. Ball, F. Barthe and S. Artstein), Probability Theory and Related Fields 129, 381-390 (2004). ps dvi pdf.
On Some Low Distortion Metric Ramsey Problems (with Y. Bartal, N. Linial and M. Mendel), Discrete and Computational Geometry 33(1), 27-45 (2005). ps dvi pdf.
On Metric Ramsey-type Dichotomies (with Y. Bartal, N. Linial and M. Mendel), Journal of the London Mathematical Society 71, no. 2, 289-303 (2005). ps dvi pdf.
Low Dimensional Embeddings of Ultrametrics (with Y. Bartal, N. Linial and M. Mendel), European Journal of Combinatorics, 25 (2004), no. 1, 87-92. ps dvi pdf.
On the maximum satisfiability of random formulas (with D. Achlioptas and Y. Peres), Journal of the Association of Computing Machinery (JACM) 54 (2007), issue 2, article no. 10. ps dvi pdf. The following conference version appeared in FOCS 2003.
Euclidean Quotients of Finite Metric Spaces (with M. Mendel), Advances in Mathematics 189(2), 451-494 (2004). ps dvi pdf.
A Probabilistic Approach to the Geometry of the l_p^n Ball (with F. Barthe, O. Guedon and S. Mendelson), Annals of Probability 33 (2005), no. 2, 480-513. ps dvi pdf.
Limitations to Frechet's Metric Embedding Method (with Y. Bartal, N. Linial and M. Mendel), Israel Journal of Mathematics 151 (2006) 111-124. ps dvi pdf.
On the Turan Number of the Hexagon (with Z. Furedi and J. Verstraete), Advances in Mathematics 203(2), 476-496 (2006). ps dvi pdf.
A Note on Bipartite Graphs without 2k-Cycles (with J. Verstraete), Probability, Combinatorics and Computing 14 (5-6), 845-849 (2005). ps dvi pdf.
Embedding the Diamond Graph in L_p and Dimension Reduction in L_1 (with J. R. Lee), Geometric and Functional Analysis (GAFA) 14(4), 745-747 (2004). ps dvi pdf. Following several requests I wrote up a proof of the classical uniform convexity inequality used in this paper. Here is a different proof of the uniform convexity inequality, written by J. Matousek.
Metric structures in L_1: Dimension, snowflakes, and average distortion (with J. R. Lee and M. Mendel), European Journal of Combinatorics 26(8), 1180-1190. ps dvi pdf. A conference version of this paper appeared in LATIN 2004.
Metric decomposition, smooth measures, and clustering (with J. R. Lee), preprint, 2003.
Absolute Lipschitz extendability (with J. R. Lee), Comptes Rendus de l'Académie des Sciences - Series I - Mathematics 338(11): 859-862, 2004. pdf .
Extending Lipschitz functions via random metric partitions (with J. R. Lee), Inventiones Mathematicae 160 (2005), no. 1, 59-95. ps dvi pdf.
Approximating the Cut-Norm via Grothendieck's Inequality (with N. Alon), SIAM Journal on Computing 35, issue 4 (STOC 2004 special issue), 787-803 (2006). ps dvi pdf. A conference version appeared in STOC 2004.
The Two Possible Values of the Chromatic Number of a Random Graph (with D. Achlioptas), Annals of Mathematics 162(3), 1333-1349 (2005). ps dvi pdf. A conference version appeared in STOC 2004.
Measured descent: A new embedding method for finite metrics (with R. Krauthgamer, J. R. Lee and M. Mendel), Geometric and Functional Analysis (GAFA) 15(4), 839-858 (2005). ps dvi pdf. A conference appeared in FOCS 2004.
Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs (with Y. Rabani and A. Sinclair), Journal of Functional Analysis 227(2), 273-303 (2005). ps dvi pdf.
Quadratic forms on graphs (with N. Alon, K. Makarychev and Y. Makarychev), Inventiones Mathematicae 163, number 3 (2006), 499-522. ps dvi pdf. A conference version appeared in STOC 2005.
Parity check matrices and product representaions of squares (with J. Verstraete), Combinatorica 28 (2008), no. 2, 163-185. ps dvi pdf. An extended abstract of some of the results in this paper, titled Improved bounds on the size of sparse parity check matrices, appeared in IEEE ISIT 2005.
Euclidean distortion and the Sparsest Cut (with S. Arora and J. R. Lee), Journal of the American Mathematical Society 21 (2008), no. 1, 1-21. ps dvi pdf. The following extended abstract appeared in STOC 2005.
Frechet embeddings of negative type metrics (with S. Arora and J. R. Lee), Discrete and Computational Geometry 38 (2007), no. 4, 726-739. ps dvi pdf.
Markov chains in smooth Banach spaces and Gromov hyperbolic metric spaces (with Y. Peres, O. Schramm and S. Sheffield), Duke Mathematical Journal 134(1), 165-197 (2006). ps dvi pdf.
Nearest neighbor preserving embeddings (with P. Indyk), ACM Transactions on Algorithms 3 (2007), no. 3, Art. 31, 12 pp. ps dvi pdf.
Some applications of Ball's extension theorem (with M. Mendel), Proceedings of the American Mathematical Society 134 (2006), 2577-2584. ps dvi pdf.
Rigorous location of phase transitions in hard optimization problems (with D. Achlioptas and Y. Peres), Nature 435, 759-764 (2005). pdf.
Metric cotype (with M. Mendel), Annals of Mathematics 168 (2008), no. 1, 247-298. ps dvi pdf. The following extended abstract appeared in SODA 2006. The following note on quasisymmetric embeddings contains another application of metric cotype.
Trees and Markov convexity (with J. R. Lee and Y. Peres), Geometric and Functional Analysis (GAFA) 18, Number 5, (2009). ps dvi pdf. The following extended abstract appeared in SODA 2006.
Nonembeddability theorems via Fourier analysis (with S. Khot), Mathematische Annalen 334, number 4, 821-852 (2006). ps dvi pdf. A conference version appeared in FOCS 2005.
Scaled Enflo type is equivalent to Rademacher type (with M. Mendel), Bulletin of the London Mathematical Society 39 (2007), no. 3, 493-498. ps dvi pdf.
Poincare inequalities, embeddings, and wild groups (with L. Silberman), Compositio Mathematica 147, no. 5, 1546-1572 (2011). ps dvi pdf.
Lower bounds on Locality Sensitive Hashing (with R. Motwani and R. Panigrahi), SIAM Journal on Discrete Mathematics 21 (2007), no. 4, 930-935. ps dvi pdf. A conference version appeared in SoCG 2006.
Planar Earthmover is not in L_1 (with G. Schechtman), SIAM Journal on Computing 37 (2007), no. 3, 804-826. ps dvi pdf. The following extended abstract appeared in FOCS 2006.
Ramsey partitions and proximity data structures (with M. Mendel), Journal of the European Mathematical Society 9(2):253-275, 2007. ps dvi pdf. The following extended abstract appeared in FOCS 2006.
L_p metrics on the Heisenberg group and the Goemans-Linial conjecture (with J. R. Lee), FOCS 2006, 99-108. ps dvi pdf.
Maximum gradient embeddings and monotone clustering (with M. Mendel), Combinatorica 30 number 5 (2010), 581-615. ps dvi pdf. An extended abstract appeared in APPROX 2007.
Markov convexity and local rigidity of distorted metrics (with M. Mendel), Journal of the European Mathematical Society, volume 15, issue 1 (2013), 287-337 ps dvi pdf. An extended abstract appeared in SOCG 2008.
A note on dichotomies for metric transforms (with M. Mendel). ps dvi pdf.
The UGC hardness threshold of the L_p Grothendieck problem (with G. Kindler and G. Schechtman), Mathematics of Operations Research, volume 35, number 2 (2010), 267-283. ps dvi pdf. An extended abstract appeared in SODA 2008.
Linear equations modulo 2 and the L_1 diameter of convex bodies (with S. Khot), SIAM Journal on Computing 38 (2008), no. 4, 1448-1463. ps dvi pdf. The following extended abstract appeared in FOCS 2007.
The Euclidean distortion of the lamplighter group (with T. Austin and A. Valette), Discrete and Computational Geometry, volume 44, issue 1 (2010), pages 55-74. ps dvi pdf.
Random martingales and localization of maximal inequalities (with T. Tao), Journal of Functional Analysis 259 (2010) 731-779. ps dvi pdf.
The wreath product of Z with Z has Hilbert compression exponent 2/3 (with T. Austin and Y. Peres), Proceedings of the American Mathematical Society 137 (2009), no. 1, 85-90. ps dvi pdf.
Embeddings of discrete groups and the speed of random walks (with Y. Peres), International Mathematics Research Notices 2008, Art. ID rnn 076, 34 pp. ps dvi pdf.
The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite (with W. B. Johnson), Discrete and Computational Geometry volume 43, issue 3 (2010), pages 542-553. ps dvi pdf. A conference version appeared in SODA 2009.
L_p compression, traveling salesmen, and stable walks (with Y. Peres), Duke Mathematical Journal vol. 157 no. 1 (2011), pages 53-108. ps dvi pdf.
Approximate kernel clustering (with S. Khot), Mathematika 55 (2009), no. 1-2, 129-165. ps dvi pdf. An extended abstract appeared in FOCS 2008.
A (\log n)^{\Omega(1)} integrality gap for the Sparsest Cut SDP (with J. Cheeger and B. Kleiner), FOCS 2009. ps dvi pdf.
Compression bounds for Lipschitz maps from the Heisenberg group to L_1 (with J. Cheeger and B. Kleiner), Acta Mathematica, volume 207, issue 2 (2011), pages 291-373. ps dvi pdf.
Sharp kernel clustering algorithms and their associated Grothendieck inequalities (with S. Khot), Random Structures and Algorithms, Volume 42, Issue 3 (2013), Pages 269-401. ps dvi pdf. An extended abstract appeared in SODA 2010.
Improved bounds in the metric cotype inequality for Banach spaces (with O. Giladi and M. Mendel), Journal of Functional Analysis 260 (2011) 164-194. ps dvi pdf. See also the related note (with O. Giladi) on improved scaled Enflo type.
L_1 embeddings of the Heisenberg group and fast estimation of graph isoperimetry, Proceedings of the International Congress of Mathematicians, volume III, 1549-1575, Hyderabad India, 2010. ps dvi pdf.
Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem (with T. Tao), Israel Journal of Mathematics 192 (2012), 489-504. ps dvi pdf.
Overlap properties of geometric expanders (with J. Fox, M. Gromov, V. Lafforgue and J. Pach), Journal für die reine und angewandte Mathematik 671, 49-83 (2012). ps dvi pdf. An extended abstract appeared in SODA 2011.
Absolutely minimal Lipschitz extension of tree-valued mappings (with S. Sheffield), Mathematische Annalen, volume 354, issue 3 (2012), pages 1049-1078. ps dvi pdf.
Sharp quantitative nonembeddability of the Heisenberg group into superreflexive Banach spaces (with T. Austin and R. Tessera), Groups, Geometry, and Dynamics, Volume 7, Issue 3 (2013), pages 497�522. ps dvi pdf.
On the Banach space valued Azuma inequality and small set isoperimetry of Alon-Roichman graphs, Combinatorics, Probability and Computing volume 21, issue 4 (2012), pages 623-634. ps dvi pdf.
Assouad's theorem with dimension independent of the snowflaking (with O. Neiman), Revista Matematica Iberoamericana, volume 28, issue no. 4 (2012), pages 1123-1142. ps dvi pdf.
Sparse quadratic forms and their geometric applications (after Batson, Spielman and Srivastava), Séminaire Bourbaki 63, no. 1033 (2011), 1-27. Published in Asterisque volume 348 (2012), pages 189-217. ps dvi pdf. See also the related technical perspective that appeared in Communications of the ACM, Vol. 56 No. 8 (2013), Page 86.
The Grothendieck constant is strictly smaller than Krivine's bound (with M. Braverman, K. Makarychev and Y. Makarychev), submitted. pdf. An extended abstract appeared in FOCS 2011.
Ultrametric subsets with large Hausdorff dimension (with M. Mendel), Inventiones Mathematicae Volume 192, Issue 1 (2013), Pages 1-54. pdf.
Grothendieck-type inequalities in combinatorial optimization (with S. Khot), Communications on Pure and Applied Mathematics Volume 65, Issue 7, pages 992-1035, 2012. pdf.
Bourgain's discretization theorem (with O. Giladi and G. Schechtman), Annales Mathematiques de la faculte des sciences de Toulouse vol. XXI, no. 4 (2012), pp. 817-837. ps dvi pdf.
Ultrametric skeletons (with M. Mendel), to appear in Proceedings of the National Academy of Sciences. ps dvi pdf.
Solution of the propeller conjecture in R^3 (with A. Jagannath and S. Heilman), Discrete and Computational Geometry Volume 50, Issue 2 (2013), Page 263-305. ps dvi pdf. An extended abstract appeared in STOC 2012. The relevant code is available here.
Discretization and affine approximation in high dimensions (with S. Li), to appear in Israel Journal of Mathematics. ps dvi pdf.
An introduction to the Ribe program, Japanese Journal of Mathematics 7 (2012), no. 2, 167-233. pdf.
Krivine schemes are optimal (with O. Regev), to appear in Proceedings of the American Mathematical Society. ps dvi pdf.
Pisier's inequality revisited (with T. Hytönen), Studia Mathematica 215 (2013), no. 3, 221-235. ps dvi pdf.
Nonlinear spectral calculus and super-expanders (with M. Mendel), to appear in Publications mathématiques de l'IHÉS. ps dvi pdf. An extended abstract announcing parts of this work, and titled "Towards a calculus for non-linear spectral gaps" appeared in SODA 2010.
Locally decodable codes and the failure of cotype for projective tensor products (with J. Briët and O. Regev), Electronic Research Announcements in Mathematical Sciences, volume 19 (2012), pages 120-130. ps dvi pdf.
Efficient rounding for the noncommutative Grothendieck inequality (with O. Regev and T. Vidick), submitted. ps dvi pdf. An extended abstract appeared in STOC 2013.
Vertical versus horizontal Poincare inequalities on the Heisenberg group (with V. Lafforgue), to appear in Israel Journal of Mathematics. ps dvi pdf.
Spectral calculus and Lipschitz extension for barycentric metric spaces (with M. Mendel), Analysis and Geometry in Metric Spaces 1 (2013), 163-199. ps dvi pdf.
Expanders with respect to Hadamard spaces and random graphs (with M. Mendel), submitted. ps dvi pdf.
Quantitative affine approximation for UMD targets (with T. Hytönen and S. Li), preprint.
Comparison of metric spectral gaps, submitted. ps dvi pdf.
A doubling subset of L_p for p>2 that is inherently infinite dimensional (with V. Lafforgue), submitted. ps dvi pdf.

Assaf Naor

Courant Institute of Mathematical Sciences
New York University
251 Mercer Street
New York, NY 10012

Office address: Warren Weaver Hall 1113
Office phone: (212) 998-3382
Fax: (212) 995-4121
email: naor@cims.nyu.edu

-->