| Publication | Date of Publication | Type |
|---|
| Rank bounds and integrality gaps for cutting planes procedures | 2026-05-29 | Paper |
| Low rank matrix-valued Chernoff bounds and approximate matrix multiplication | 2017-09-29 | Paper |
Low rank matrix-valued Chernoff bounds and approximate matrix multiplication
(available as arXiv preprint) | 2017-09-29 | Paper |
How well can primal-dual and local-ratio algorithms perform?
ACM Transactions on Algorithms | 2014-09-09 | Paper |
| On quadratic threshold CSPs | 2014-03-25 | Paper |
| On the tightening of the standard SDP for vertex cover with _1 inequalities | 2012-10-24 | Paper |
SDP gaps from pairwise independence
Theory of Computing | 2012-09-27 | Paper |
| Tight gaps for vertex cover in the Sherali-Adams SDP hierarchy | 2012-08-31 | Paper |
Toward a model for backtracking and dynamic programming
Computational Complexity | 2012-06-26 | Paper |
Rank bounds and integrality gaps for cutting planes procedures
Theory of Computing | 2011-05-24 | Paper |
Integrality gaps of 2-o(1) for vertex cover SDPs in the Lovász-Schrijver hierarchy
SIAM Journal on Computing | 2011-04-04 | Paper |
Online embeddings
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2010-09-10 | Paper |
A sublinear algorithm for weakly approximating edit distance
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Sublinear geometric algorithms
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Girth and euclidean distortion
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
Extending SDP integrality gaps to Sherali-Adams with applications to quadratic programming and MaxCutGain
Integer Programming and Combinatorial Optimization | 2010-06-22 | Paper |
On quadratic threshold CSPs
LATIN 2010: Theoretical Informatics | 2010-04-27 | Paper |
Integrality gaps of semidefinite programs for vertex cover and relations to \(\ell_1\) embeddability of negative type metrics
SIAM Journal on Discrete Mathematics | 2010-03-17 | Paper |
Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-10-28 | Paper |
Optimal Sherali-Adams Gaps from Pairwise Independence
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-10-28 | Paper |
Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to ℓ1 Embeddability of Negative Type Metrics
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-02-17 | Paper |
Near Optimal Dimensionality Reductions That Preserve Volumes
Lecture Notes in Computer Science | 2008-11-27 | Paper |
Analysis of set-up time models: a metric perspective
Theoretical Computer Science | 2008-07-31 | Paper |
Vertex Cover Resists SDPs Tightened by Local Hypermetric Inequalities
Integer Programming and Combinatorial Optimization | 2008-06-10 | Paper |
Approximate range searching in higher dimension
Computational Geometry | 2007-10-19 | Paper |
Dimensionality reductions in \(\ell_{2}\) that preserve volumes and distance to affine spaces
Discrete & Computational Geometry | 2007-10-11 | Paper |
A Rigorous Analysis for Set-Up Time Models – A Metric Perspective
Lecture Notes in Computer Science | 2007-09-10 | Paper |
Monotone Circuits for the Majority Function
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2007-08-28 | Paper |
Sublinear Geometric Algorithms
SIAM Journal on Computing | 2006-06-01 | Paper |
Computing and Combinatorics
Lecture Notes in Computer Science | 2006-01-11 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2006-01-10 | Paper |
Simple permutations mix well
Theoretical Computer Science | 2006-01-09 | Paper |
Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
SIAM Journal on Computing | 2005-10-28 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2005-08-24 | Paper |
Metric embeddings -- beyond one-dimensional distortion
Discrete & Computational Geometry | 2004-12-16 | Paper |
| scientific article; zbMATH DE number 2079416 (Why is no real title available?) | 2004-07-28 | Paper |
| scientific article; zbMATH DE number 1775401 (Why is no real title available?) | 2004-02-08 | Paper |
| scientific article; zbMATH DE number 2019638 (Why is no real title available?) | 2003-12-17 | Paper |
Least-distortion Euclidean embeddings of graphs: Products of cycles and expanders
Journal of Combinatorial Theory. Series B | 2002-12-10 | Paper |
Girth and Euclidean distortion
Geometric and Functional Analysis. GAFA | 2002-07-29 | Paper |
Low distortion Euclidean embeddings of trees
Israel Journal of Mathematics | 2000-06-05 | Paper |
