Questions tagged [sum-of-squares]
The sum-of-squares tag has no usage guidance.
22
questions
2
votes
0answers
68 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 ...
2
votes
1answer
104 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$ ...
2
votes
0answers
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)$$
...
4
votes
0answers
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 ...
1
vote
0answers
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
votes
0answers
483 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
96 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
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)]$ ...
3
votes
0answers
134 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
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, ...
3
votes
1answer
178 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
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 $...
4
votes
1answer
112 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 ...
10
votes
3answers
648 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
vote
0answers
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 ...
8
votes
1answer
909 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
258 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
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 ...
4
votes
1answer
575 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
603 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 ...
25
votes
2answers
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?
...
10
votes
1answer
526 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 ...
