Applications to Computer Science, Statistics

• On the optimality of the random hyperplane rounding technique for MAX CUT (with U. Feige), Random Structures \& Algorithms, 20 (2002), 403--440.
• On the integrality ratio of semidefinite relaxations of MAX CUT, (with U. Feige, a short version of the paper above), Proceedings of the thirty-third annual ACM symposium on Theory of computing (2001), 433--442.
• On Characterization of Two-Sample $U$-Statistic (with E. Schechtman), Statistics & Probability Letters, 58 (2002), 53--59.
• Graphs with tiny vector chromatic numbers and huge chromatic numbers (with U. Feige and M. Langberg), SICOMP, volume 33, issue 6 , 1338--1368 (2004).
• The Shattering dimension of sets of linear functionals (with S. Mendelson), Ann. Prob., 32 (2004), 1746--1770.
• Complexity Measures of Sign Matrices (with N. Linial, S. Mendelson and A. Shraibman), Combinatorica 27 (2007), no. 4, 439--463.
• Planar earthmover is not in $L_1$ (with A. Naor), SIAM Journal on Computing, 37 Issue 3, 804-826 (2007) (short version in proceedings of FOCS 2006).
• The UGC hardness threshold of the Lp Grothendieck problem (with G. Kindler and A. Naor), Mathematics of Operations Research 35 (2010 ), 267-283 (extended abstract in SODA 2008).
• Lower bounds for local versions of dimension reductions (with Adi Shraibman), Discrete Comput. Geom. 41 (2009), no. 2, 273--283.
• Lower bounds on quantum multiparty communication complexity (with T. Lee and A. Shraibman), proceedings of the 24th Conference on Computational Complexity, p. 254--262, 2009.
• Diamond graphs and super-reflexivity (with W.B. Johnson), J. Topol. Anal. 1 (2009), no. 2, 177--189.