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
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.
Robust algorithms for Maximum Independent Set on Minor-free graphs based on the Sherali-Adams Hierarchy.
With M. Moharrami. APPROX 2009
On the nonexistence of Dimension Reduction in $\ell_2^2$. With M. Moharrami. CCCG 08.
Nearly tight dimensionality reductions that preserve volumes
With A. Zouzias. RANDOM 2008.
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.
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.
A rigorous analysis for set-up time models - a metric perspective.
With E. Bachmat and T. Lam. Theoretical Computer Science.
Monotone circuits for the majority function.
With S. Hoory and T. Pitassi. RANDOM 2006.
How well can primal-dual and local-ratio algorithms perform?
With A. Borodin and D. Cashman. ICALP 2005.
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.
On-line algorithms for market equilibria.
With S Angelopoulos, A. Das Sarma and T. Viglas. COCOON 2005.
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).
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)
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).
A Sublinear Algorithm for Weakly Approximating Edit Distance.
With T. Batu, F. Ergun, J. Kilian, S. Raskhodnikova, R. Rubinfeld and R. Sami
STOC 2003. pspdf
Sublinear Geometric Algorithms. With B. Chazelle and D. Liu.
SICOMP 35(3): 627-646 (2005) (preliminary version in STOC 2003). pspdf
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).
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
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.
GAFA, Geometric and Functional Analysis. 12: pp 380-394 (2002).
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).
Trees and Euclidean Metrics. With
N. Linial and M. Saks.
STOC 98 version ps
and version in Israel Journal of Methematics, 106 pp 339-348 (1998).