Questions tagged [sum-of-squares]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
49 views

Maximum degree of the Sum of Squares certificate of a non-negative degree d polynomial on the boolean hypercube

Let $f: \{0, 1\}^n \rightarrow \mathbb R$ be a polynomial on the boolean hypercube. If $f$ is non-negative $(f \geq 0)$ i.e. $f(x) \geq 0, \forall x \in \{0, 1\}^n$ then $f$ always has a degree $2n$ ...
Subhadeep's user avatar
  • 111
2 votes
0 answers
83 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 ...
ckamath's user avatar
  • 223
2 votes
1 answer
195 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$ ...
learning's user avatar
2 votes
0 answers
41 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)$$ ...
guigux's user avatar
  • 121
4 votes
0 answers
250 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 ...
VS.'s user avatar
  • 539
1 vote
0 answers
103 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}=...
Turbo's user avatar
  • 12.8k
12 votes
0 answers
504 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 $\...
Mason's user avatar
  • 229
3 votes
0 answers
103 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 ...
gradstudent's user avatar
  • 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)]$ ...
gradstudent's user avatar
  • 1,443
3 votes
0 answers
153 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" :...
gradstudent's user avatar
  • 1,443
2 votes
0 answers
74 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, ...
gradstudent's user avatar
  • 1,443
3 votes
1 answer
182 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 ...
gradstudent's user avatar
  • 1,443
1 vote
0 answers
35 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 $...
gradstudent's user avatar
  • 1,443
4 votes
1 answer
115 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 ...
gradstudent's user avatar
  • 1,443
10 votes
3 answers
758 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 ...
gradstudent's user avatar
  • 1,443
1 vote
0 answers
61 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 ...
Student's user avatar
  • 654
8 votes
1 answer
1k 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 ...
anurag anshu's user avatar
2 votes
1 answer
337 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 ...
Chao Liao's user avatar
7 votes
0 answers
317 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 ...
Steve's user avatar
  • 451
4 votes
1 answer
632 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 ...
Martin Vatshelle's user avatar
13 votes
2 answers
633 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 ...
Jeremy Kun's user avatar
  • 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? ...
Anonymous's user avatar
  • 4,031
10 votes
1 answer
546 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 ...
mkatkov's user avatar
  • 537