# Tag Info

19

The basic sum-of-squares proof system, introduced under the name of Positivstellensatz refutations by Grigoriev and Vorobjov, is a “static” proof system for showing that a set of polynomial equations and inequations $$S=\{f_1=0,\dots,f_k=0,h_1\ge0,\dots,h_m\ge0\},$$ where $f_1,\dots,f_k,h_1,\dots,h_m\in\mathbb R[x_1,\dots,x_n]$, has no common solution in $\... 12 SOS can be considered as a proof system where lines are of the form$p(\vec{x}) \geq 0$where$p(\vec{x})$is a polynomial in variables$\vec{x}$. The inference rules are:$\over x^2-x \geq 0\over x-x^2 \geq 0\over p(\vec{x})^2\geq 0p(\vec{x}) \geq 0 \over p(\vec{x})x \geq 0p(\vec{x}) \geq 0 \over p(\vec{x})(1-x) \geq 0p_1(\vec{x}) \geq 0, \...

10

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].) To be honest, I've never tried to understand these papers and would be happy if someone dumbed them down for me. One notable consequence of this work is ...

9

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 definite $X\succ 0$ that satisfies the affine constraints $\mathrm{tr}(A_i^T X) = b_i$. I would guess this is satisfied for any SDP you can find in the ...

9

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 Nullstellensatz as stated in the question is indeed its special case. Other comments asked for lecture notes with a proof of the Positivstellensatz, and as I do not ...

6

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,$$ $$\mathbb{\tilde E} x^2 = 0, \quad \mathbb{\tilde E} x^3 = 0,$$ $$\mathbb{\tilde E} x^4 = 1$$ Then $\mathbb{\tilde E}P^2 = 0$ but $\mathbb{\tilde E} PQ = 1$. This is ...

3

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 be no SDP relaxations for exact Max-CUT of size $2^{n^c}$ for some $c < 1$. I think this means there can be no SOS proof of degree $n^c$, and hence there ...

2

Linear regression Yes. For linear regression, you can do both updates in $O(1)$ time. Recall that for ordinary least squares estimation, we estimate the parameter vector $\hat\beta$ using the equation $$\hat{\beta} = (X^T X)^{-1} X^T y.$$ Here $X$ is a $n \times 2$ matrix and $y$ is a $n$-vector. Adding a point amounts to adding a row to $X$ and $y$; ...

1

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 0$ for every $x\in \{-1,1\}^n$. As you write, it is trivially true that $c^*=\mathsf{OPT}(G)$ is the optimal value where this holds by definition, but for one, ...

1

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 variables in it). You can write this as $L = MD$ where $M$ is a matrix with rows indexed by the monomials $m$ and columns indexed by the points $x \in \{\pm 1\}$, with ...

1

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 A_i \preceq B$ is badly behaved if here is an objective function $c$ for which the SDP $\sup c^T x \,\, s.t. \,\, \sum_{i=1}^m x_i A_i \preceq B$ has a finite ...

1

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 Monique Laurent's surveys and the references therein). It is known that that the hierarchy is monotone (it's not hard to see that a degree $l$ psuedo-distribution is ...

1

I think my answer is probably insufficient, but it remains for completeness' sake (although see Boaz's comments below for probably a better answer) When we limit ourselves to boolean variables, the claim can be seen when $(x_i^2-1) \in E$ for all $i \in[n]$ with the observation that degree $2n$ pseudo-distributions are actual distributions, that is, suppose ...

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