Electronic Colloquium on Computational Complexity
Login | Register | Classic Style

Reports tagged with Semidefinite programming:
TR95-011 | 15th February 1995
Roman Bacik, Sanjeev Mahajan

Semidefinite Programming and its Applications to NP Problems

The graph homomorphism problem is a canonical $NP$-complete problem.
It generalizes various other well-studied problems such as graph
coloring and finding cliques. To get a better insight into a
combinatorial problem, one often studies relaxations of the problem.
We define fractional homomorphisms and pseudo-homomorphisms ... more >>>

TR00-043 | 21st June 2000
Uriel Feige, Marek Karpinski, Michael Langberg

A Note on Approximating MAX-BISECTION on Regular Graphs

We design a $0.795$ approximation algorithm for the Max-Bisection problem
restricted to regular graphs. In the case of three regular graphs our
results imply an approximation ratio of $0.834$.

more >>>

TR03-030 | 27th February 2003
Amin Coja-Oghlan, Andreas Goerdt, André Lanka, Frank Schädlich

Certifying Unsatisfiability of Random 2k-SAT Formulas using Approximation Techniques

Abstract. It is known that random k-SAT formulas with at least
(2^k*ln2)*n random clauses are unsatisfiable with high probability. This
result is simply obtained by bounding the expected number of satisfy-
ing assignments of a random k-SAT instance by an expression tending
to 0 when n, the number of variables ... more >>>

TR06-063 | 1st May 2006
Moses Charikar, Konstantin Makarychev, Yury Makarychev

Approximation Algorithm for the Max k-CSP Problem

We present a c.k/2^k approximation algorithm for the Max k-CSP problem (where c > 0.44 is an absolute constant). This result improves the previously best known algorithm by Hast, which has an approximation guarantee of Omega(k/(2^k log k)). Our approximation guarantee matches the upper bound of Samorodnitsky and Trevisan up ... more >>>

TR06-064 | 1st May 2006
Moses Charikar, Konstantin Makarychev, Yury Makarychev

Note on MAX 2SAT

In this note we present an approximation algorithm for MAX 2SAT that given a (1 - epsilon) satisfiable instance finds an assignment of variables satisfying a 1 - O(sqrt{epsilon}) fraction of all constraints. This result is optimal assuming the Unique Games Conjecture.

The best previously known result, due ... more >>>

TR06-098 | 17th August 2006
Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani

A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover

We study semidefinite programming relaxations of Vertex Cover arising from
repeated applications of the LS+ ``lift-and-project'' method of Lovasz and
Schrijver starting from the standard linear programming relaxation.

Goemans and Kleinberg prove that after one round of LS+ the integrality
gap remains arbitrarily close to 2. Charikar proves an integrality ... more >>>

TR06-152 | 6th December 2006
Konstantinos Georgiou, Avner Magen, Iannis Tourlakis

Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy

We prove that the integrality gap after tightening the standard LP relaxation for Vertex Cover with Omega(sqrt(log n/log log n)) rounds of the SDP LS+ system is 2-o(1).

more >>>

TR08-008 | 8th February 2008
Venkatesan Guruswami, Prasad Raghavendra

Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness

Revisions: 1

We study the approximability of the \maxcsp problem over non-boolean domains, more specifically over $\{0,1,\ldots,q-1\}$ for some integer $q$. We obtain a approximation algorithm that achieves a ratio of $C(q) \cdot k/q^k$ for some constant $C(q)$ depending only on $q$. Further, we extend the techniques of Samorodnitsky and Trevisan to ... more >>>

TR08-104 | 23rd November 2008
Madhur Tulsiani

CSP Gaps and Reductions in the Lasserre Hierarchy

We study integrality gaps for SDP relaxations of constraint satisfaction problems, in the hierarchy of SDPs defined by Lasserre. Schoenebeck recently showed the first integrality gaps for these
problems, showing that for MAX k-XOR, the ratio of the SDP optimum to the integer optimum may be as large as ... more >>>

TR09-129 | 30th November 2009
Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer

Subsampling Semidefinite Programs and Max-Cut on the Sphere

Revisions: 1

We study the question of whether the value of mathematical programs such as
linear and semidefinite programming hierarchies on a graph $G$, is preserved
when taking a small random subgraph $G'$ of $G$. We show that the value of the
Goemans-Williamson (1995) semidefinite program (SDP) for \maxcut of $G'$ is
more >>>

TR10-169 | 10th November 2010
Siavosh Benabbas, Konstantinos Georgiou, Avner Magen

The Sherali-Adams System Applied to Vertex Cover: Why Borsuk Graphs Fool Strong LPs and some Tight Integrality Gaps for SDPs

Revisions: 2

We study the performance of the Sherali-Adams system for VERTEX COVER on graphs with vector
chromatic number $2+\epsilon$. We are able to construct solutions for LPs derived by any number of Sherali-Adams tightenings by introducing a new tool to establish Local-Global Discrepancy. When restricted to
$O(1/ \epsilon)$ tightenings we show ... more >>>

TR10-177 | 16th November 2010
Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu

Bypassing UGC from some optimal geometric inapproximability results

Revisions: 1

The Unique Games conjecture (UGC) has emerged in recent years as the starting point for several optimal inapproximability results. While for none of these results a reverse reduction to Unique Games is known, the assumption of bijective projections in the Label Cover instance seems critical in these proofs. In this ... more >>>

TR11-066 | 25th April 2011
Venkatesan Guruswami, Ali Kemal Sinop

Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives

Revisions: 1

We present an approximation scheme for optimizing certain Quadratic Integer Programming problems with positive semidefinite objective functions and global linear constraints. This framework includes well known graph problems such as Minimum graph bisection, Edge expansion, Uniform sparsest cut, and Small Set expansion, as well as the Unique Games problem. These ... more >>>

TR12-111 | 5th September 2012
Venkatesan Guruswami, Ali Kemal Sinop

Faster SDP hierarchy solvers for local rounding algorithms

Convex relaxations based on different hierarchies of
linear/semi-definite programs have been used recently to devise
approximation algorithms for various optimization problems. The
approximation guarantee of these algorithms improves with the number
of {\em rounds} $r$ in the hierarchy, though the complexity of solving
(or even writing down the solution for) ... more >>>

TR13-184 | 23rd December 2013
Boaz Barak, Jonathan Kelner, David Steurer

Rounding Sum-of-Squares Relaxations

We present a general approach to rounding semidefinite programming relaxations obtained by the Sum-of-Squares method (Lasserre hierarchy). Our approach is based on using the connection between these relaxations and the Sum-of-Squares proof system to transform a *combining algorithm* -- an algorithm that maps a distribution over solutions into a (possibly ... more >>>

TR14-059 | 21st April 2014
Boaz Barak, David Steurer

Sum-of-squares proofs and the quest toward optimal algorithms

Revisions: 2

In order to obtain the best-known guarantees, algorithms are traditionally tailored to the particular problem we want to solve. Two recent developments, the Unique Games Conjecture (UGC) and the Sum-of-Squares (SOS) method, surprisingly suggest that this tailoring is not necessary and that a single efficient algorithm could achieve best possible ... more >>>

TR15-053 | 7th April 2015
Massimo Lauria, Jakob Nordström

Tight Size-Degree Bounds for Sums-of-Squares Proofs

We exhibit families of 4-CNF formulas over n variables that have sums-of-squares (SOS) proofs of unsatisfiability of degree (a.k.a. rank) d but require SOS proofs of size n^{Omega(d)} for values of d = d(n) from constant all the way up to n^{delta} for some universal constant delta. This shows that ... more >>>

TR16-058 | 12th April 2016
Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin

A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem

We prove that with high probability over the choice of a random graph $G$ from the Erd\H{o}s-R\'enyi distribution $G(n,1/2)$, the $n^{O(d)}$-time degree $d$ Sum-of-Squares semidefinite programming relaxation for the clique problem will give a value of at least $n^{1/2-c(d/\log n)^{1/2}}$ for some constant $c>0$.
This yields a nearly tight ... more >>>

TR16-141 | 11th September 2016
Ryan O'Donnell

SOS is not obviously automatizable, even approximately

Revisions: 1

Suppose we want to minimize a polynomial $p(x) = p(x_1, \dots, x_n)$, subject to some polynomial constraints $q_1(x), \dots, q_m(x) \geq 0$, using the Sum-of-Squares (SOS) SDP hierarachy. Assume we are in the "explicitly bounded" ("Archimedean") case where the constraints include $x_i^2 \leq 1$ for all $1 \leq i \leq ... more >>>

TR17-011 | 22nd January 2017
Boaz Barak, Pravesh Kothari, David Steurer

Quantum entanglement, sum of squares, and the log rank conjecture

For every constant $\epsilon>0$, we give an $\exp(\tilde{O}(\sqrt{n}))$-time algorithm for the $1$ vs $1-\epsilon$ Best Separable State (BSS) problem of distinguishing, given an $n^2\times n^2$ matrix $M$ corresponding to a quantum measurement, between the case that there is a separable (i.e., non-entangled) state $\rho$ that $M$ accepts with probability $1$, ... more >>>

ISSN 1433-8092 | Imprint