Questions tagged [sum-of-squares]
The sum-of-squares tag has no usage guidance.
3
votes
0answers
135 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 ...
1
vote
0answers
97 views
Complexity of planted root of a system of quadratic homogeneous polynomials?
Given homogeneous degree $2$ randomly chosen polynomials $f_1,\dots,f_{m}$ in $\mathbb Z[x_1,\dots,x_n,y_1,\dots,y_n]$ each with only monomials $x_iy_j$ with condition that the system $f_1=\dots=f_{m}=...
3
votes
0answers
53 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 ...
12
votes
0answers
430 views
Is satisfying $\sum_{i=1}^{n}{x_i^{y_i}}=r$ NP Complete?
Question
I would like to show that satisfying $\sum_{i=1}^{n}{x_i^{y_i}}=r$ is NP-Complete.
Consider $L= \{(\bar{y},r):\exists \bar{x} \text{ such that } \sum_{i=1}^{n}{x_i^{y_i}}=r\}$.
Where $\...
3
votes
0answers
89 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 ...
3
votes
0answers
107 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)]$ ...
3
votes
0answers
109 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" :...
2
votes
0answers
63 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, ...
3
votes
1answer
168 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 ...
1
vote
0answers
27 views
How does one know what is not in a certain class of pseudo-distributions?
We consider working in the function space $\mathbb{R}^{\{ -1,1\}^n}$ where the expectation inner-product makes the juntas form a $2^n$ dimensional orthonormal basis.
Now say one has found a degree $...
4
votes
1answer
97 views
From Lasserre maps to pseudo-distributions
Let me define a ``Lasserre map of degree $d$" as a linear map $L : \mathbb{R}_n[x] \rightarrow \mathbb{R}$ i.e a real valued linear map on polynomials over $n$ variables with real coeffients. This is ...
1
vote
0answers
52 views
About increasing the objective values of certificates for Max-Clique SDP
Say you write a round-k Lasserre (or any other hierarchy!) SDP relaxation of the Max-Clique problem. Lets say one now finds (or knows how to sample with high probability) a graph $G_1$ of size $n$ and ...
7
votes
1answer
663 views
Positivstellensatz and sum of squares method
This question comes from many online resources that introduce Sum-of-Squares method, such as the survey of Barak and Steurer (http://arxiv.org/abs/1404.5236). Let me focus on Theorem 2.1 of this ...
2
votes
1answer
155 views
How to prove $\tilde{\mathbb{E}}PQ=0$ when $\tilde{\mathbb{E}}P^2 = 0$?
Let $\tilde{\mathbb{E}}$ be a degree-$r$ pseudo-distribution. If $\tilde{\mathbb{E}}P^2 = 0$, how to prove that $\tilde{\mathbb{E}}PQ=0$ for all polynomials $Q$ such that $\mathrm{deg}(PQ)\le r$?
We ...
7
votes
0answers
288 views
Why is it so difficult to study Sum of Squares (SoS) algorithms with degree $d>4$?
In many publications on the computational complexity of Sum of Squares (SoS) algorithms, it is typical to study the degree-$4$ relaxation; e.g.
Rounding Sum-of-Squares Relaxations
Sum-of-Squares ...
4
votes
1answer
197 views
Complexity of iterative least squares regression
Given a set of points $P = \{(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n) \}$ one can use least squares method to fit a polynomial to $P$.
In particular I am interested in linear and quadratic regression.
I ...
13
votes
2answers
559 views
Numerical precision in sum-of-squares method?
I have been reading a bit about the sum-of-squares method (SOS) from the survey of Barak & Steurer and the lecture notes of Barak. In both cases they sweep issues of numerical accuracy under the ...
23
votes
2answers
1k views
Sum-of-squares proof system
Recently I have seen several articles on arxiv that refer to a proof system called sum-of-squares.
Can someone explain what is a sum-of-squares proof and why such proofs are important/interesting?
...
