Research Interests.

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

Professional Activities.

Teaching.

• Current teaching (at Princeton): Topics in Analysis (MAT 529).
• Past teaching (at NYU).
• 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.
• Spring 2014: Topics in Geometric Nonlinear Functional Analysis.

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 $$\ell_p^n$$, $$1 < p < 2$$, into $$\ell_1^{(1+\varepsilon) 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 $$\ell_p^n$$ (with D. Romik), Annales de l'Institut Henri Poincaré (B), Probability and Statistics 39 (2003), 241-261. ps dvi pdf.
• The Surface Measure and Cone Measure on the Sphere of $$\ell_p^n$$, Transactions of the American Mathematical Society 359 (2007), 1045-1079. ps dvi pdf.
• Lipschitz Sums of Convex Functions (with M. Csörnyei), Studia Mathematica 158 (2003), 269-286. ps dvi pdf.
• Hyperplane Projections of the Unit Ball of $$\ell_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. Csörnyei), 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 $$\ell_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.
• Poincaré 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 $$\mathbb{Z}$$ with $$\mathbb{Z}$$ has Hilbert compression exponent $$\frac{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), Forum of Mathematics, Pi, Volume 1/2013, e4. 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), Proceedings of the National Academy of Sciences (2013), 110 (48), 19251-19255. ps dvi pdf.
• Solution of the propeller conjecture in $$\mathbb{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), Israel Journal of Mathematics, Volume 197, Issue 1 (2013), pp. 107-129. 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), Proceedings of the American Mathematical Society 142 (2014), no. 12, 4315-4320. 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), Publications mathématiques de l'IHÉS 119, issue 1 (2014), pages 1-95. 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), Theory of Computing 10(11), 2014, 257-295. ps dvi pdf. An extended abstract appeared in STOC 2013.
• Vertical versus horizontal Poincaré inequalities on the Heisenberg group (with V. Lafforgue), Israel Journal of Mathematics Volume 203 (2014), Issue 1, pages 309-339. 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), to appear in Duke Mathematical Journal. ps dvi pdf. An extended abstract appeared in ITCS 2014.
• Comparison of metric spectral gaps, Analysis and Geometry in Metric Spaces 2 (2014), pages 1-52. ps dvi pdf.
• A doubling subset of $$L_p$$ for $$p > 2$$ that is inherently infinite dimensional (with V. Lafforgue), Geometriae Dedicata, Volume 172, Issue 1, pages 387-398 (2014). ps dvi pdf.
• Metric $$X_p$$ inequalities (with G. Schechtman), submitted. ps dvi pdf.
• Pythagorean powers of hypercubes (with G. Schechtman), submitted. ps dvi pdf.
• Quantitative affine approximation for UMD targets (with T. Hytönen and S. Li), preprint.

 Princeton UniversityDepartment of MathematicsFine Hall, Washington Road Princeton, NJ 08544-1000, USA Office address: Fine Hall 1005 Office phone: +1 609-258-4198 Fax: +1 609-258-1367 email: naor@math.princeton.edu
-->