10 votes
Accepted

When is the duality gap of semidefinite programming (SDP) zero?

There is a more complicated theory of duality for SDPs that is exact: there is no 'extra condition' like Slater's condition. This is due to Ramana. (For another take on this involving SOS, see [KS12]...
Ryan O'Donnell's user avatar
9 votes

When is the duality gap of semidefinite programming (SDP) zero?

For the SDP in standard form $$ \min\{ \mathrm{tr}(C^T X): \mathrm{tr}(A_1^T X) = b_1, \ldots, \mathrm{tr}(A_m^T X) = b_m, X \succeq 0\}, $$ Slater's condition reduces to the existence of a positive ...
Sasho Nikolov's user avatar
9 votes
Accepted

Positivstellensatz and sum of squares method

As already noted in the comments, the question is based on a misunderstanding; the actual Positivstellensatz is a stronger statement than Artin’s theorem on nonnegative polynomials, and the real ...
Emil Jeřábek's user avatar
6 votes
Accepted

How to prove $\tilde{\mathbb{E}}PQ=0$ when $\tilde{\mathbb{E}}P^2 = 0$?

That implication is not actually true. Consider $P$, $Q$, and the pseudodistribution given by: $$P = x, \quad Q = x^3,$$ $$r = 4,$$ $$\mathbb{\tilde E} 1 = 1, \quad \mathbb{\tilde E} x = 0,$$ $$\...
Jonathan Shi's user avatar
3 votes

SOS hardness of $Max-2-Lin(\mathbb{Z}_2)$?

We don't have integrality gaps even for Max-CUT, even for degree 4. See Barak and Steurer's notes, at the end. You might be interested in Lee Raghavendra Steurer '14. They seem to be saying there can ...
Whosyourjay's user avatar
1 vote
Accepted

Sum-of-Squares Certificates

I see the confusion, but I think the document you provided pretty well explains what is meant: solving MAXCUT on a graph $G$ is equivalent to finding the smallest value of $c$ such that $c-f_G(x)\geq ...
Jason Gaitonde's user avatar
1 vote

From Lasserre maps to pseudo-distributions

The answer to your first question is yes by some linear algebra. Write down the equations for $L(m) = \sum_{x\in\pm 1} D(x)m(x)$ where $m$ is a monomial of degree at most $d$ (with no squared ...
Andrew Morgan's user avatar
1 vote

When is the duality gap of semidefinite programming (SDP) zero?

There is a nice (I think....) characterization of when strong duality holds, or fails for {\em all} objective functions. We say that the semidefinite {\em system} $(P_{SD}) \,\, \sum_{i=1}^m x_i ...
district9's user avatar
1 vote
Accepted

Numerical precision in sum-of-squares method?

Here is Boaz Barak's comment on the issue: We do sweep numerical accuracy under the rug -- the more "traditional" SOS literature of Parrilo, Lasserre etc.. deals with these issues (e.g., see ...

Only top scored, non community-wiki answers of a minimum length are eligible