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.

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+.

Lovdsz and Schrijver (1991) defined three progressively stronger procedures LS0, LS and LS+, for systematically tightening linear relaxations over many rounds. All three procedures yield the integral hull after at most n rounds. On the other hand, constant rounds of LS+can derive the relaxations behind many famous approximation algorithms such as those for MAX-CUT, SPARSEST-CUT. So proving round lower bounds for these procedures on specific problems may give evidence about inapproximability. We prove new round lower bounds for vertex cover in the LS hierarchy. Arora et al. (2006) showed that the integrality gap for VERTEX COVER relaxations remains 2 - o(1) even after Omega(log n) rounds LS. However, their method can only prove round lower bounds as large as the girth of the input graph, which is O(log n) for interesting graphs. We break through this "girth barrier" and show that the integrality gap for VERTEX COVER remains 1.5 - epsi even after Omega(log2n) rounds of LS. In contrast, the best PCP-based results only rule out 1.36-approximations. Moreover, we conjecture that the new technique we introduce to prove our lower bound, the "fence" method, may lead to linear or nearly linear LS round lower bounds for VERTEX COVER

Lovasz and Schrijver described a generic method of tightening the LP and SDP relaxation for any 0-1 optimization problem. These tightened relaxations were the basis of several celebrated approximation algorithms (such as for max-cu , max-3sat, and sparsest cut).We prove strong inapproximability results in this model for well-known problems such as max-3sat, hypergraph vertex cover and set cover. We show that the relaxations produced by as many as Ω(n) rounds of the LS+ procedure do not allow nontrivial approximation, thus ruling out the possibility that the LS+ approach gives even slightly subexponential approximation algorithms for these problems.We also point out why our results are somewhat incomparable to known inapproximability results proved using PCPs, and formalize several interesting open questions.

The arguments used by R. Kannan (1984), L. Fortnow (1997), and Lipton-Viglas (1999) are generalized and combined with a new argument for diagonalizing over machines taking n bits of advice on inputs of length n to obtain the first nontrivial time-space lower bounds for SAT on non-uniform machines. In particular we show that for any a 0 and any /spl epsiv/0 and all rationals r/spl ges/1, DTISP(n/sup r/, n/sup l-/spl epsiv//)/spl sub//spl ne/NTIM E(n/sup r/). We show how extending our uniform separations can lead to a separation of SC and NP.