# Questions tagged [sum-of-squares]

The tag has no usage guidance.

22 questions
Filter by
Sorted by
Tagged with
522 views

### Systematic studies of sum of quadratic polynomials squared

I'm wondering if there exists systematic studies of sums of quadratic forms squared, similar to the quadratic forms, which is practically reflected in eigenvalue decomposition (that has huge practical ...
89 views

### Sum-of-Squares Certificates

We say that $f$ has a degree $2d$ sum-of-squares certificate if $f=\sum_{i=1}^r (g_i(x))^2$, where for each $i\in[r]$, we have that $g_i$ is a polynomial of degree at most $d$. Thus showing that $f$ ...
246 views

588 views

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

I haven't been able to find in the literature a precise characterization of the vanishing of the SDP duality gap. Or, when does "strong duality" hold? For example, when one goes back and forth ...
101 views

98 views

### Primal/Dual of the Lasserre/ SOS SDP hierarchy

Sum of Squares proofs and the Lasserre hierarchy can both be stated as SDPs. It is often claimed without proof that these SDPs are dual to each other, although I do not see that this is obvious. I was ...
92 views

### Some questions about the Ryan O'Donnel and Yuan Zhou's paper “Approximability and proof complexity”

My question is particularly about the set-up in section $8$ (Analysis of the KV Max-Cut instances") of the paper, https://arxiv.org/pdf/1211.1958.pdf. What they call the Khot-Vishnoi UG instance ...
110 views

### Can the Lasserre relaxation be defined over the reals?

If one wants to say minimize a function $f : \{-1,1\}^n \rightarrow \mathbb{R}$ on its domain then a degree$-d$ Lasserre relaxation of it would be to solve the problem of $\min \mathbb{E}_\mu [f(x)]$ ...
128 views

### SOS and the small set expansion property

For what graphs do we know that their small set expansion property has a low degree SOS proof? Is this known to be true for say the complete graphs? A terminology issue about what is low degree" :...
70 views

### Is there a relationship between the probabilistic interepretation of Sherali-Adams SDP hierarchy and the Lasserre SDP hierarchy?

Firstly note this paper http://ttic.uchicago.edu/~madhurt/Papers/reductions.pdf where a Lasserre SDP is being setup for the independent set probblem at the bottom of page 4 where the author says says, ...
### SOS hardness of $Max-2-Lin(\mathbb{Z}_2)$?
Do we know of instances of $Max-2-Lin(\mathbb{Z}_2)$ which have a integrality gaps w.r.t to high degree (> 4) SOS relaxations? Or if we specialize to Max-CUT do we know of graphs whose Max-CUT ...