publications

  • Extending SDP Integrality Gaps to Sherali-Adams with Applications to Quadratic Programming and MaxCutGain, with Siavosh Benabbas. To appear in Conference on Integer Programming and Combinatorial Optimization (IPCO) 2010.

  • On Quadratic Threshold CSPs
    With Per Austrin and Siavosh Benabbas. To appear in LATIN 2010.

  • On the Tightening of the Standard SDP for Vertex Cover with l1 Inequalities
    With K. Georgiou and I. Tourlakis. 29th Foundations of Software Technology and Theoretical Computer Science (FSTTCS) 2009

  • Optimal Sherali-Adams Gaps from Pairwise Independence. 
    With K. Georgiou and M. Tulsiani. APPROX 2009. pdf

  • Robust algorithms for Maximum Independent Set on Minor-free graphs based on the Sherali-Adams Hierarchy. 
    With M. Moharrami. APPROX 2009 pdf

  • On the nonexistence of Dimension Reduction in $\ell_2^2$.
    With M. Moharrami. CCCG 08. pdf

  • Nearly tight dimensionality reductions that preserve volumes  
    With A. Zouzias. RANDOM 2008. pdf

  • Vertex Cover Resists SDPs Tightened by Local Hypermetric Inequalities.
    With K. Georgiou and I. Tourlakis. 13th Conference on Integer Programming and Combinatorial Optimization (IPCO 2008). pdf

  • Integrality gaps of 2-o(1) for vertex cover SDPs in the Lovasz-Schrijver hierarchy.
    With K. Georgiou, T. Pitassi and I. Tourlakis.
    FOCS 2007. pdf

  • Integrality gaps of semidefinite programs for Vertex Cover and relations to $\ell_1$ embeddability of Negative Type metrics. 
    With H. Hatami and V. Markakis. APPROX 2007. ps   pdf

  • A rigorous analysis for set-up time models - a metric perspective.  
    With E. Bachmat and T. Lam. Theoretical Computer Science. pdf

  • Monotone circuits for the majority function.  
    With S. Hoory and T. Pitassi. RANDOM 2006. pdf

  • How well can primal-dual and local-ratio algorithms perform?  
    With A. Borodin and D. Cashman. ICALP 2005. ps   pdf

  • Toward a Model for Backtracking and Dynamic Programming.  
    With M. Alekhnovich, A. Borodin, J. Buresh-Oppenheim, R. Impagliazzo and T. Pitassi. CCC (Conference on Computational Complexity) 2005. ps   pdf

  • On-line algorithms for market equilibria.  
    With S Angelopoulos, A. Das Sarma and T. Viglas. COCOON 2005. ps   pdf

  • Approximating Range Searching in Higher Dimension.  
    With B. Chazelle and D. Liu.
    CCCG 2004 - Canadian Conference on Computational Geometry.

  • Metric embeddings beyond one-dimensional distortion.  
    With R. Krauthgamer and N. Linial.
    Discrete & Computational Geometry 31(3): 339-356 (2004). ps   pdf

  • Simple Permutations Mix Well.  
    With S. Hoory, S. Myers and C. Rackoff. special issue of Theoretical Computer Science 348(2-3): 251-261 (2005) (preliminary version in ICALP 2004) ps   pdf

  • Embedding Hamming-distance of Boxes into Euclidean Space (Manuscript).
    Here are slides from a talk presented in DIMACS Workshop on Discrete Metric Spaces and their Algorithmic Applications, Princeton, Aug 2003.

  • On Cutting-plane Rank and the role of Expansion.  
    With J. Buresh-Oppenheim, N. Galesi, S. Hoory and T. Pitassi.
    Theory of Computing (2): 65--90 (2006) (preliminary version in FOCS 2003). ps   pdf

  • A Sublinear Algorithm for Weakly Approximating Edit Distance.  
    With T. Batu, F. Ergun, J. Kilian, S. Raskhodnikova, R. Rubinfeld and R. Sami
    STOC 2003. ps  pdf

  • Sublinear Geometric Algorithms.  
    With B. Chazelle and D. Liu.
    SICOMP 35(3): 627-646 (2005) (preliminary version in STOC 2003). ps  pdf

  • Sublinear approximation of Euclidean minimum spanning tree.  
    With A. Czumaj, F. Ergun, L. Fortnow, R. Rubinfeld, I. Newman, and C. Sohler.
    SICOMP (1): 91-109 (2005) (preliminary version in SODA 2003). ps  pdf

  • Dimensionality Reductions that Preserve Volumes and Distance to Affine Spaces, and their Algorithmic Applications. Discrete & Computational Geometry 38(1): 139-153 (2007). Preliminary version in RANDOM 2002. ps   pdf

  • On the Euclidicity of Metric Spaces. Ph.D. Thesis, Hebrew University (2002). Thesis advisor: Professor Nathan Linial.

  • Designing oligo libraries taking alternative splicing into account.  
    With A. Shoshan, V. Grebinskiy, A. Scolnicov, E. Fink, D. Lehavi and A. Wasserman.
    Proc. SPIE 4266, May 2001.

  • Girth and Euclidean Distortion.  
    With N. Linial and A. Naor.
    STOC 2002 ps   pdf  and
    GAFA, Geometric and Functional Analysis. 12: pp 380-394 (2002). ps   pdf

  • Least-distortion Euclidean embeddings of graphs: Products of cycles and expanders.  
    With N. Linial.
    Journal of Combinatorial Theory ser. B, 79 pp 157-171 (2000). ps   pdf  

  • Trees and Euclidean Metrics.  
    With N. Linial and M. Saks.
    STOC 98 version ps   pdf and version in Israel Journal of Methematics, 106 pp 339-348 (1998). ps   pdf