Proceedings of the National Academy of Sciences: guest editor of the
Special Feature on Quantitative Geometry. The introduction of the PNAS special feature is available
here and its table of contents is available here.
Israel Journal of Mathematics: guest editor of the
special volume in the memory of Joram Lindenstrauss (A. Naor and G. Schechtman eds.). The introduction to the special volume (with G. Schechtman) is available here or (through Springer Link)
here.
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: psdvipdf.
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.
psdvipdf.
A Phase Transition Phenomenon Between the Isometric and Isomorphic Extension Problems for
Holder Functions Between \(L_p\) Spaces, Mathematika 48 (2001), 253-271.
psdvipdf.
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.
psdvipdf.
The Surface Measure and Cone Measure on the Sphere of \(\ell_p^n\),
Transactions of the American Mathematical Society 359 (2007), 1045-1079.
psdvipdf.
Lipschitz Sums of Convex Functions (with M.
Csörnyei), Studia Mathematica 158 (2003), 269-286.
psdvipdf.
Hyperplane Projections of the Unit
Ball of \(\ell_p^n\) (with F.
Barthe), Discrete and Computational Geometry 27
(2002), no. 2, 215- 226.
psdvipdf.
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.
psdvipdf.
Girth and Euclidean Distortion (with N.
Linial and A. Magen),
Geometric and Functional Analysis (GAFA)12 (2002), no. 2,
380-394.
psdvipdf
. 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. psdvipdf.
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.
psdvipdf.
Entropy Jumps in the Presence of a Spectral Gap (with K. Ball and F.
Barthe), Duke Mathematical Journal 119, No. 1, 41-63
(2003).
psdvipdf.
On Metric Ramsey Type Phenomena (with Y.
Bartal, N. Linial and M. Mendel),
Annals of Mathematics 162(2), 643-709 (2005). psdvipdf. 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).
psdvipdf.
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).
psdvipdf.
On Some Low Distortion Metric Ramsey Problems
(with Y. Bartal, N. Linial and M. Mendel), Discrete and Computational
Geometry 33(1), 27-45 (2005).
psdvipdf.
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).
psdvipdf.
Low Dimensional Embeddings of Ultrametrics (with
Y. Bartal, N. Linial and M. Mendel), European Journal
of Combinatorics, 25 (2004), no. 1, 87-92.
psdvipdf.
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.
psdvipdf.
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). psdvipdf.
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.
psdvipdf.
Limitations to Frechet's Metric Embedding Method
(with Y. Bartal, N. Linial and M. Mendel), Israel Journal of Mathematics 151 (2006) 111-124.
psdvipdf.
On the Turan Number of the Hexagon (with Z.
Furedi and J. Verstraete), Advances in Mathematics 203(2), 476-496 (2006).
psdvipdf.
A Note on Bipartite Graphs without \(2k\)-Cycles (with J. Verstraete),
Probability, Combinatorics and Computing 14 (5-6), 845-849 (2005).
psdvipdf.
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.
psdvipdf.
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. psdvipdf.
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).
psdvipdf. 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).
psdvipdf. 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).
psdvipdf. 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).
psdvipdf.
Quadratic forms on graphs (with N. Alon, K. Makarychev and Y. Makarychev), Inventiones Mathematicae 163, number 3 (2006), 499-522.
psdvipdf. 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.
psdvipdf. 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.
psdvipdf.
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.
psdvipdf.
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).
psdvipdf.
Nearest neighbor preserving embeddings (with P. Indyk),
ACM Transactions on Algorithms 3 (2007), no. 3, Art. 31, 12 pp.
psdvipdf.
Some applications of Ball's extension theorem (with M. Mendel), Proceedings of the American Mathematical Society 134 (2006), 2577-2584.
psdvipdf.
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.
psdvipdf.
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).
psdvipdf.
The following extended abstract
appeared in SODA 2006.
Nonembeddability theorems via Fourier analysis
(with S. Khot), Mathematische Annalen 334, number 4, 821-852 (2006).
psdvipdf. 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.
psdvipdf.
Poincaré inequalities, embeddings, and wild groups
(with L. Silberman), Compositio Mathematica 147, no. 5, 1546-1572 (2011). psdvipdf.
Lower bounds on Locality Sensitive Hashing
(with R. Motwani and R. Panigrahi), SIAM Journal on Discrete Mathematics 21 (2007), no. 4, 930-935.
psdvipdf. 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.
psdvipdf.
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.
psdvipdf.
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. psdvipdf.
Maximum gradient embeddings and monotone clustering
(with M. Mendel), Combinatorica 30 number 5 (2010), 581-615. psdvipdf. 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 psdvipdf. An extended abstract appeared in SoCG 2008.
A note on dichotomies for metric transforms
(with M. Mendel). psdvipdf.
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. psdvipdf. 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. psdvipdf. 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. psdvipdf.
Random martingales and localization of maximal inequalities
(with T. Tao), Journal of Functional Analysis 259 (2010) 731-779. psdvipdf.
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. psdvipdf.
Embeddings of discrete groups and the speed of random walks
(with Y. Peres), International Mathematics Research Notices 2008, Art. ID rnn 076, 34 pp. psdvipdf.
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. psdvipdf. 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. psdvipdf.
Approximate kernel clustering
(with S. Khot), Mathematika 55 (2009), no. 1-2, 129-165. psdvipdf. 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. psdvipdf.
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. psdvipdf.
Sharp kernel clustering algorithms and their associated Grothendieck inequalities
(with S. Khot), Random Structures and Algorithms, Volume 42, Issue 3 (2013), Pages 269-401. psdvipdf. 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. psdvipdf. 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. psdvipdf.
Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
(with T. Tao), Israel Journal of Mathematics 192 (2012), 489-504. psdvipdf.
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). psdvipdf. 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. psdvipdf.
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. psdvipdf.
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. psdvipdf.
Assouad's theorem with dimension independent of the snowflaking
(with O. Neiman), Revista Matematica Iberoamericana, volume 28, issue no. 4 (2012), pages 1123-1142. psdvipdf.
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.
psdvipdf. 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. psdvipdf.
Ultrametric skeletons
(with M. Mendel), Proceedings of the National Academy of Sciences (2013), 110 (48), 19251-19255. psdvipdf.
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. psdvipdf. 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. psdvipdf.
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. psdvipdf.
Pisier's inequality revisited
(with T. Hytönen), Studia Mathematica 215 (2013), no. 3, 221-235. psdvipdf.
Nonlinear spectral calculus and super-expanders
(with M. Mendel), Publications mathématiques de l'IHÉS 119, issue 1 (2014), pages 1-95. psdvipdf. 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. psdvipdf.
Efficient rounding for the noncommutative Grothendieck inequality
(with O. Regev and T. Vidick), Theory of Computing 10(11), 2014, 257-295. psdvipdf. 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. psdvipdf.
Spectral calculus and Lipschitz extension for barycentric metric spaces
(with M. Mendel), Analysis and Geometry in Metric Spaces 1 (2013), 163-199. psdvipdf.
Expanders with respect to Hadamard spaces and random graphs
(with M. Mendel), Duke Mathematical Journal 164 (2015), no. 8, 1471-1548. psdvipdf. An extended abstract appeared in ITCS 2014.
Comparison of metric spectral gaps, Analysis and Geometry in Metric Spaces 2 (2014), pages 1-52. psdvipdf.
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). psdvipdf.
Metric \(X_p\) inequalities (with G. Schechtman), Forum of Mathematics, Pi, Volume 4 (2016), e3, 81 pp. psdvipdf.
Pythagorean powers of hypercubes (with G. Schechtman), Annales de l'Institut Fourier 66 no. 3 (2016), pages 1093-1116. psdvipdf.
On Lipschitz extension from finite subsets (with Y. Rabani), Israel Journal of Mathematics 219 (2017), Issue 1, pages 115-161. psdvipdf.
Uniform nonextendability from nets, Comptes Rendus de l'Académie des
Sciences - Series I - Mathématique 353 (2015), no. 11, 991-994. psdvipdf.
Quantitative affine approximation for UMD targets (with T. Hytönen and S. Li), Discrete Analysis 2016, Paper No. 6, 48 pp. psdvipdf.
Snowflake universality of Wasserstein spaces
(with A. Andoni and O. Neiman), Annales scientifiques de l'École normale supérieure, (4) 51 (2018), no. 3, 657-700. pdf.
Restricted invertibility revisited
(with P. Youssef), Journey Through Discrete Mathematics. A Tribute to Jiří Matoušek (2017), pages 657-691. psdvipdf.
Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost (with A. Andoni and O. Neiman), Proceedings of ICALP 2016, 83:1-15.
pdf.
Discrete Riesz transforms and sharp metric \(X_p\) inequalities, Annals of Mathematics, Volume 184 (2016), Issue 3, pages 991-1016. psdvipdf.
Heat flow and quantitative differentiation
(with T. Hytönen), Journal of the European Mathematical Society
Volume 21, Issue 11, 2019, pages 3415-3466. psdvipdf.
The integrality gap of the Goemans-Linial SDP relaxation for Sparsest Cut is at least a constant multiple of \(\sqrt{\log n}\)
(with R. Young), Proceedings of STOC 2017, pages 564-575. psdvipdf.
A spectral gap precludes low-dimensional embeddings, Proceedings of SoCG 2017, 50:1-16.
pdf.
Vertical perimeter versus horizontal perimeter
(with R. Young), Annals of Mathematics 188 (2018), no. 1, 171-279.
pdf.
Impossibility of dimension reduction in the nuclear norm
(with G. Pisier and G. Schechtman), Discrete and Computational Geometry, 63 (2020), pages 319–345.
pdf. An extended abstract appeared in Proceedings of SODA 2018, pages 1345-1352.
Data-dependent hashing via nonlinear spectral gaps
(with A. Andoni, A. Nikolov, I. Razenshteyn, E. Waingarten), Proceedings of STOC 2018, pages 787-800. pdf.
Metric dimension reduction: A snapshot of the Ribe program,
Proceedings of the 2018 International Congress of Mathematicians,
Rio de Janeiro, Volume 1 (2018), 759-837.
pdf.
Hölder homeomorphism and approximate nearest neighbors
(with A. Andoni, A. Nikolov, I. Razenshteyn, E. Waingarten), Proceedings of FOCS 2018, 159-169. pdf.
The Andoni–Krauthgamer–Razenshteyn characterization of sketchable norms fails for sketchable metrics
(with S. Khot), to appear in Harmonic Analysis and
Applications, Springer Lecture Notes in Mathematics.
pdf. An extended abstract appeared in Proceedings of SODA 2019, 1814-1824.
Nonpositive curvature is not coarsely universal
(with A. Eskenazis and M. Mendel), Inventiones mathematicae volume 217, issue 3 (2019), pages 833-886.
pdf.
Moments of the distance between independent random vectors (with K. Oleszkiewicz), Geometric Aspects of Functional Analysis, Springer Lecture
Notes in Mathematics 2266, Volume II (2020), pages 229-256. pdf.
An average John theorem, to appear in Geometry & Topology. pdf.
Concentration of Markov chains with bounded moments (with S. Rao and O. Regev), Annales de l'Institut
Henri Poincaré Probabilitiés et Statistiques 56 (2020), no. 3, 2270–2280. pdf.
Rates in the vector-valued law of large numbers for Markov chains, preprint.
Krivine diffusions attain the Goemans–Williamson approximation ratio (with R. Eldan). pdf.
Foliated corona decompositions
(with R. Young), submitted. pdf.
Impossibility of almost extension, to appear in Advances in Mathematics. pdf.
An approximation scheme for quadratic form
maximization on convex bodies (with G. Schechtman), preprint.
A framework for quadratic form maximization
over convex sets through non-convex relaxations (with V. Bhattiprolu and E. Lee). An extended abstract will
appear in STOC 2021, full version forthcoming soon.