We give the first tight integrality gap for Vertex Cover in the Sherali-Adams SDP system. More precisely, we show that for every \epsilon >0, the standard SDP for Vertex Cover that is strengthened with the level-6 Sherali-Adams system has integrality gap 2-\epsilon. To the best of our knowledge this is the first nontrivial tight integrality gap for the Sherali-Adams SDP hierarchy for a combinatorial problem with hard constraints. For our proof we introduce a new tool to establish Local-Global Discrepancy which uses simple facts from high-dimensional geometry. This allows us to give Sherali-Adams solutions with objective value n(1/2+o(1)) for graphs with small (2+o(1)) vector chromatic number. Since such graphs with no linear size independent sets exist, this immediately gives a tight integrality gap for the Sherali-Adams system for superconstant number of tightenings. In order to obtain a Sherali-Adams solution that also satisfies semidefinite conditions, we reduce semidefiniteness to a condition on the Taylor expansion of a reasonably simple function that we are able to establish up to constant-level SDP tightenings. We conjecture that this condition holds even for superconstant levels which would imply that in fact our solution is valid for superconstant level Sherali-Adams SDPs.

In this paper we develop algorithms for approximating matrix multiplication with respect to the spectral norm. Let A ∊ ℝn×m and B ∊ ℝn×p be two matrices and ε > 0. We approximate the product A⊤ B using two sketches and , where t ≪ n, such that with high probability. We analyze two different sampling procedures for constructing and ; one of them is done by i.i.d. non-uniform sampling rows from A and B and the other by taking random linear combinations of their rows. We prove bounds on t that depend only on the intrinsic dimensionality of A and B, that is their rank and their stable rank. For achieving bounds that depend on rank when taking random linear combinations we employ standard tools from high-dimensional geometry such as concentration of measure arguments combined with elaborate ε-net constructions. For bounds that depend on the smaller parameter of stable rank this technology itself seems weak. However, we show that in combination with a simple truncation argument it is amenable to provide such bounds. To handle similar bounds for row sampling, we develop a novel matrix-valued Chernoff bound inequality which we call low rank matrix-valued Chernoff bound. Thanks to this inequality, we are able to give bounds that depend only on the stable rank of the input matrices. We highlight the usefulness of our approximate matrix multiplication bounds by supplying two applications. First we give an approximation algorithm for the ℓ2-regression problem that returns an approximate solution by randomly projecting the initial problem to dimensions linear on the rank of the constraint matrix. Second we give improved approximation algorithms for the low rank matrix approximation problem with respect to the spectral norm.

We consider a model (BT) for backtracking algorithms. Our model generalizes both the priority model of Borodin, Nielson and Rackoff, as well as a simple dynamic programming model due to Woeginger, and hence spans a wide spectrum of algorithms. After witnessing the strength of the model, we then show its limitations by providing lower bounds for algorithms in this model for several classical problems such as interval scheduling, knapsack and satisfiability.

We define an algorithmic paradigm, the stack model, that captures many primal-dual and local-ratio algorithms for approximating covering and packing problems. The stack model is defined syntactically and without any complexity limitations and hence our approximation bounds are independent of the P versus NP question. Using the stack model, we bound the performance of a broad class of primal-dual and local-ratio algorithms and supply a (log n +1)/2 inapproximability result for set cover, a 4/3 inapproximability for min Steiner tree, and a 0.913 inapproximability for interval scheduling on two machines.

Linear and semidefinite programming are highly successful approaches for obtaining good approximations for NP-hard optimization problems. For example, breakthrough approximation algorithms for Max Cut and Sparsest Cut use semidefinite programming. Perhaps the most prominent NP-hard problem whose exact approximation factor is still unresolved is Vertex Cover. Probabilistically checkable proof (PCP)-based techniques of Dinur and Safra [Ann. of Math./ (2), 162 (2005), pp. 439–486] show that it is not possible to achieve a factor better than 1.36; on the other hand no known algorithm does better than the factor of 2 achieved by the simple greedy algorithm. There is a widespread belief that semidefinite programming (SDP) techniques are the most promising methods available for improving upon this factor of 2. Following a line of study initiated by Arora et al. [Theory Comput., 2 (2006), pp. 19–51], our aim is to show that a large family of linear programming (LP)- and SDP-based algorithms fail to produce an approximation for Vertex Cover better than 2. Lovász and Schrijver [SIAM J. Optim., 1 (1991), pp. 166–190] introduced the systems $LS$ and $LS_+$ for systematically tightening LP and SDP relaxations, respectively, over many rounds. These systems naturally capture large classes of LP and SDP relaxations; indeed, $LS_+$ captures the celebrated SDP-based algorithms for Max Cut and Sparsest Cut mentioned above. We rule out polynomial-time SDP-based $2-\Omega(1)$ approximations for Vertex Cover using $LS_+$. In particular, for every $\epsilon>0$ we prove an integrality gap of $2-\epsilon$ for Vertex Cover SDPs obtained by tightening the standard LP relaxation with $\Omega(\sqrt{\log n/\log\log n})$ rounds of $LS_+$. While tight integrality gaps were known for Vertex Cover in the weaker $LS$ system [G. Schoenebeck, L. Trevisan, and M. Tulsiani, Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM Press, New York, 2007, pp. 302–310], previous results did not rule out a $2-\Omega(1)$ approximation after even two rounds of $LS_+$.

We show that the integrality gap of the standard SDP for \vc~on instances of $n$ vertices remains $2-o(1)$ even after the addition of \emph{all} hypermetric inequalities. Our lower bound requires new insights into the structure of SDP solutions behaving like $\ell_1$ metric spaces when one point is removed. We also show that the addition of all $\ell_1$ inequalities eliminates any solutions that are not convex combination of integral solutions. Consequently, we provide the strongest possible separation between hypermetrics and $\ell_1$ inequalities with respect to the tightening of the standard SDP for \vc.

We study various semidefinite programming (SDP) formulations for Vertex Cover by adding different constraints to the standard formulation. We show that Vertex Cover cannot be approximated better than $2-O(\sqrt{\log\log n/\log n})$ even when we add the so-called pentagonal inequality constraints to the standard SDP formulation, and thus almost meet the best upper bound known due to Karakostas [Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, 2005], of $2-\Omega(\sqrt{1/\log n})$. We further show the surprising fact that by strengthening the SDP with the (intractable) requirement that the metric interpretation of the solution embeds into $\ell_1$ with no distortion, we get an exact relaxation (integrality gap is 1), and on the other hand, if the solution is arbitrarily close to being $\ell_1$ embeddable, the integrality gap is $2-o(1)$. Finally, inspired by the above findings, we use ideas from the integrality gap construction of Charikar [SODA '02: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2002, pp. 616–620] to provide a family of simple examples for negative type metrics that cannot be embedded into $\ell_1$ with distortion better than $8/7-\epsilon$. To this end we prove a new isoperimetric inequality for the hypercube.

Linear and semidefinite programming are highly successful approaches for obtaining good approximations for NP-hard optimization problems. For example, breakthrough approximation algorithms for Max Cut and Sparsest Cut use semidefinite programming. Perhaps the most prominent NP-hard problem whose exact approximation factor is still unresolved is Vertex Cover. PCP-based techniques of Dinur and Safra [7] show that it is not possible to achieve a factor better than 1.36; on the other hand no known algorithm does better than the factor of 2 achieved by the simple greedy algorithm. Furthermore, there is a widespread belief that SDP technicptes are the most promising methods available for improving upon this factor of 2. Following a line of study initiated by Arora et al. [3], our aim is to show that a large family of LP and SDP based algorithms fail to produce an approximation for Vertex Cover better than 2. Lovasz and Schrijver [21] introduced the systems LS and LS+for systematically tightening LP and SDP relaxations, respectively, over many rounds. These systems naturally capture large classes of LP and SDP relaxations; indeed, LS+captures the celebrated SDP-based algorithms for Max Cur and Sparsest Cur mentioned above. We rule out polynomial-time 2 - Omega(lfloor) approximations for Vertex Cover using LS+. In particular, we prove an integrality gap of 2 - o(lfloor)for Vertex Cover SDPs obtained by tightening the standard LP relaxation with Omega(radiclog n/ log log n) rounds of LS+. While tight integrality gaps were known for Vertex Cover in the weaker LS system [23 ], previous results did not rule out a2 - Omega(1) approximation after even two rounds of LS+.

We initiate an investigation of sublinear algorithms for geometric problems in two and three dimensions. We give optimal algorithms for intersection detection of convex polygons and polyhedra, point location in two-dimensional triangulations and Voronoi diagrams, and ray shooting in convex polyhedra, all of which run in expected time $O(\sqrt{n}\,)$, where n is the size of the input. We also provide sublinear solutions for the approximate evaluation of the volume of a convex polytope and the length of the shortest path between two points on the boundary.

We consider the problem of computing the weight of a Euclidean minimum spanning tree for a set of n points in $\mathbb R^d$. We focus on the setting where the input point set is supported by certain basic (and commonly used) geometric data structures that can provide efficient access to the input in a structured way. We present an algorithm that estimates with high probability the weight of a Euclidean minimum spanning tree of a set of points to within $1 + \eps$ using only $\widetilde{\O}(\sqrt{n} \, \text{poly} (1/\eps))$ queries for constant d. The algorithm assumes that the input is supported by a minimal bounding cube enclosing it, by orthogonal range queries, and by cone approximate nearest neighbor queries.

We present a new method for proving rank lower bounds for Cutting Planes (CP) and several procedures based on lifting due to Lovasz and Schrijver (LS), when viewed as proof systems for unsatisfiability. We apply this method to obtain the following new results: first, we prove near-optimal rank bounds for Cutting Planes and Lovasz-Schrijver proofs for several prominent unsatisfiable CNF examples, including random kCNF formulas and the Tseitin graph formulas. It follows from these lower bounds that a linear number of rounds of CP or LS procedures when applied to relaxations of integer linear programs is not sufficient for reducing the integrality gap. Secondly, we give unsatisfiable examples that have constant rank CP and LS proofs but that require linear rank resolution proofs. Thirdly, we give examples where the CP rank is O(log n) but the LS rank is linear. Finally, we address the question of size versus rank: we show that, for both proof systems, rank does not accurately reflect proof size. Specifically, there are examples with polynomial-size CP/LS proofs, but requiring linear rank.

We show how to determine whether the edit distance between two given strings is small in sublinear time. Specifically, we present a test which, given two n-character strings A and B, runs in time o(n) and with high probability returns "CLOSE" if their edit distance is O(nΑ), and "FAR" if their edit distance is Ω(n), where Α is a fixed parameter less than 1. Our algorithm for testing the edit distance works by recursively subdividing the strings A and B into smaller substrings and looking for pairs of substrings in A, B with small edit distance. To do this, we query both strings at random places using a special technique for economizing on the samples which does not pick the samples independently and provides better query and overall complexity. As a result, our test runs in time Õ(nmax(Α/2, 2Α - 1\)) for any fixed Α < 1. Our algorithm thus provides a trade-off between accuracy and efficiency that is particularly useful when the input data is very large.We also show a lower bound of Ω(nΑ/2) on the query complexity of every algorithm that distinguishes pairs of strings with edit distance at most nΑ from those with edit distance at least n/6.

We initiate an investigation of sublinear algorithms for geometric problems in two and three dimensions. We give optimal algorithms for intersection detection of convex polygons and polyhedra, point location in two-dimensional Delaunay triangulations and Voronoi diagrams, and ray shooting in convex polyhedra, all of which run in time O(√n), where n is the size of the input. We also provide sublinear solutions for the approximate evaluation of the volume of a convex polytope and the length of the shortest path between two points on the boundary.

(MATH) In this paper we partially prove a conjecture that was raised by Linial, London and Rabinovich in \cite{llr}. Let $G$ be a $k$-regular graph, $k \ge 3$, with girth $g$. We show that every embedding $f : G \to \ell_2$ has distortion $\Omega (\sqrt{g})$. The original conjecture which remains open is that the Euclidean distortion is bounded below by $\Omega(g)$. Two proofs are given, one based on semi-definite programming, and the other on Markov Type, a concept that considers random walks on metrics.

Introduction There has been a growing interest in finite metric spaces and their approximations. Such considerations have proved useful in a number of graph algorithms [13], in clustering [11] and most recently in online computation [2, 3]. To study a given metric space, one seeks first an approximate metric from a better-understood class of metrics. Thus, approximations by l 1 metrics are instrumental in the study of multicommodity flows Institute of Computer Science, Hebrew University, Jerusalem 91904, Israel. E-mail: [email protected]. Supported in part by grants from the Israeli Academy of Sciences and the US-Israel Binational Science Foundation Israel-USA. y Institute of Computer Science, Hebrew University, Jerusalem 91904, Israel. E-mail: [email protected]. z Department of Mathematics, Rutgers University, Hill Center, 110 Frelinghuysen Road, Piscataway, NJ 08854. Supported in part by NSF under gran