# Tag Info

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

### 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 ...
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 ...
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,$$ \...

### 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 ...
1 vote
Accepted

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