 |
Email:
Research Interests: Analysis; Probability; Convex Geometry; Applications of the above to combinatorics, mathematical physics and theoretical computer science.
Selected Works:
Geometric Problems in Non-Linear Functional Analysis. M.Sc. Thesis, Hebrew University (1998). Thesis advisor: Professor Joram Lindenstrauss.
Linear and Non-Linear Geometric Problems in Banach Spaces. Ph.D. Thesis, Hebrew University (2002). Thesis advisor: Professor Joram Lindenstrauss.
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.
A Phase Transition Phenomenon Between the Isometric and Isomorphic Extension Problems for Holder Functions Between L_p Spaces, Mathematika 48 (2001), 253-271.
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.
The Surface Measure and Cone Measure on the Sphere of l_p^n, Transactions of the American Mathematical Society 359 (2007), 1045-1079.
Lipschitz Sums of Convex Functions (with M. Csornyei), Studia Mathematica 158 (2003), 269-286.
Hyperplane Projections of the Unit Ball of l_p^n (with F. Barthe), Discrete and Computational Geometry 27 (2002), no. 2, 215- 226.
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.
Girth and Euclidean Distortion (with N. Linial and A. Magen), Geometric and Functional Analysis (GAFA)12 (2002), no. 2, 380-394. The following conference version has appeared in STOC 2002.
Remarks on Non Linear type and Pisier's Inequality (with G. Schechtman), Journal fur die reine und angewandte mathematik (Crelle's Journal) 552 (2002) 213-236.
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.
Entropy Jumps in the Presence of a Spectral Gap (with K. Ball and F. Barthe), Duke Mathematical Journal 119, No. 1, 41-63 (2003).
On Metric Ramsey Type Phenomena (with Y. Bartal, N. Linial and M. Mendel), Annals of Mathematics 162(2), 643-709 (2005). 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).
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).
On Some Low Distortion Metric Ramsey Problems (with Y. Bartal, N. Linial and M. Mendel), Discrete and Computational Geometry 33(1), 27-45 (2005).
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).
Low Dimensional Embeddings of Ultrametrics (with Y. Bartal, N. Linial and M. Mendel), European Journal of Combinatorics, 25 (2004), no. 1, 87-92.
On the maximum satisfiability of random formulas (with D. Achlioptas and Y. Peres), Journal of the Association of Computing Machinary (JACM) 54 (2007), issue 2, article no. 10. 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).
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.
Limitations to Frechet's Metric Embedding Method (with Y. Bartal, N. Linial and M. Mendel), Israel Journal of Mathematics 151 (2006) 111-124.
On the Turan Number of the Hexagon (with Z. Furedi and J. Verstraete), Advances in Mathematics 203(2), 476-496 (2006).
A Note on Bipartite Graphs without 2k-Cycles (with J. Verstraete), Probability, Combinatorics and Computing 14 (5-6), 845-849 (2005).
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). Following several requests I wrote up a proof of the classical uniform convexity inequality used in this paper.
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. A conference version of this paper appeared in LATIN 2004.
Metric decomposition, smooth measures, and clustering (with J. R. Lee), preprint.
Absolute Lipschitz extendability (with J. R. Lee), Comptes Rendus de l'Académie des Sciences - Series I - Mathematics 338(11): 859-862, 2004.
Extending Lipschitz functions via random metric partitions (with J. R. Lee), Inventiones Mathematicae 160 (2005), no. 1, 59-95.
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). 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). 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). 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).
Quadratic forms on graphs (with N. Alon, K. Makarychev and Y. Makarychev), Inventiones Mathematicae 163, number 3 (2006), 499-522. A conference version appeared in STOC 2005.
Parity check matrices and product representaions of squares (with J. Verstraete), to appear in Combinatorica. 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), to appear in the Journal of the American Mathematical Society. The following extended abstract appeared in STOC 2005.
Frechet embeddings of negative type metrics (with S. Arora and J. R. Lee), to appear in Discrete and Computational Geometry.
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).
Nearest neighbor preserving embeddings (with P. Indyk), to appear in the ACM Transactions on Algorithms.
Some applications of Ball's extension theorem (with M. Mendel), Proceedings of the American Mathematical Society 134 (2006), 2577-2584.
Rigorous location of phase transitions in hard optimization problems (with D. Achlioptas and Y. Peres), Nature 435, 759-764 (2005).
Metric cotype (with M. Mendel), to appear in the Annals of Mathematics. 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), to appear in Geometric and Functional Analysis (GAFA). The following extended abstract appeared in SODA 2006.
Nonembeddability theorems via Fourier analysis (with S. Khot), Mathematische Annalen 334, number 4, 821-852 (2006). A conference version appeared in FOCS 2005.
Scaled Enflo type is equivalent to Rademacher type (with M. Mendel), Bulletin of the London Mathematical Society doi: 10.1112/blms/bdm016. (2007).
Poincare inequalities, embeddings, and wild groups (with L. Silberman), preprint.
Lower bounds on Locality Sensitive Hashing (with R. Motwani and R. Panigrahi), To appear in SIAM Journal on Discrete Mathematics. A conference version appeared in SoCG 2006.
Planar Earthmover is not in L_1 (with G. Schechtman), submitted. To appear in SIAM Journal on Computing. 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. The following extended abstract appeared in FOCS 2006.
Improved bounds in the metric cotype inequality for Banach spaces (with M. Mendel), preprint.
L_p metrics on the Heisenberg group and the Goemans-Linial conjecture (with J. R. Lee), submitted. An extended abstract appeared in FOCS 2006.
Spectral inequalities on curved spaces (with Y. Rabani), preprint.
Maximum gradient embeddings and monotone clustering (with M. Mendel), submitted.
Markov convexity and local rigidity of distorted metrics (with M. Mendel), preprint.
 Update your faculty profile
|
