# Questions tagged [sum-of-squares]

The tag has no usage guidance.

20 questions
Filter by
Sorted by
Tagged with
33 views

### Are those two Sum-Of-Squares approach for unconstrained polynomial optimization related? [closed]

This is a crosspost of mathoverflow/345282 I found 2 approaches to solve an unconstrained polynomial optimization problem using the Lasserre / SOS hierarchy: $$\inf_{x\in\mathbb{R}^n}\quad p(x)$$ ...
188 views

### Testing emptiness property complexity in Sum of Squares Proof systems

Take the set $$\mathcal T=\{f_1(x_1,\dots,x_n)=\dots=f_m(x_1,\dots,x_n)=0, h_1(x_1,\dots,x_n)\geq a_1,\dots,h_t(x_1,\dots,x_n)\geq a_t\}$$ where h_1(x_1,\dots,x_n),\dots,h_t(x_1,\dots,x_n)\in\mathbb ...
99 views

90 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 ...
108 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)]$ ...
116 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" :...
65 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, ...
172 views

### 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 ...
27 views