Questions tagged [sum-of-squares]
The sum-of-squares tag has no usage guidance.
22
questions
2
votes
0
answers
71
views
Complexity of (Graph) Ramsey Theorem in Sum-of-Squares Proof System
(One formulation of) Ramsey's theorem states that any colouring of edges of the complete graph with $4^n$ vertices with two colours will contain a monochromatic clique of size $n$. I am new to proof ...
- 213
2
votes
1
answer
113
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$ ...
- 53
2
votes
0
answers
37
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)$$
...
- 121
4
votes
0
answers
247
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 ...
- 529
1
vote
0
answers
101
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}=...
- 12.5k
12
votes
0
answers
488
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 $\...
- 229
3
votes
0
answers
97
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 ...
- 1,443
3
votes
0
answers
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)]$ ...
- 1,443
3
votes
0
answers
138
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" :...
- 1,443
2
votes
0
answers
72
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, ...
- 1,443
3
votes
1
answer
179
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,443
1
vote
0
answers
33
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 $...
- 1,443
4
votes
1
answer
113
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,443
10
votes
3
answers
671
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 ...
- 1,443
1
vote
0
answers
60
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 ...
- 644
8
votes
1
answer
941
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 ...
- 193
2
votes
1
answer
293
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 ...
- 23
7
votes
0
answers
307
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 ...
- 451
4
votes
1
answer
595
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 ...
- 1,319
13
votes
2
answers
608
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 ...
- 1,318
25
votes
2
answers
2k
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?
...
- 3,993
10
votes
1
answer
527
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 ...
- 537