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.
pspdf
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.
pspdf
On-line algorithms for market equilibria.
With S Angelopoulos, A. Das Sarma and T. Viglas. COCOON 2005.
pspdf
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)
pspdf
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).
pspdf
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).
pspdf
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