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$ Sum of Squares (SoS) certificate of non-negativity i.e. $f$ can be represented as $f(x) = \sum_{i=1}^k g_i^2(x)$, where each polynomial $g_i: \{0, 1\}^n \rightarrow \mathbb R$ is of degree at most $n$.

My question is if $f$ is of degree $d$, what can you say about the maximum degree of the SoS certificate? This is equivalent to asking what can be the maximum degree of each $g_i$. Is it also $n$ or can it be much smaller like $d$ or some polynomial in $d$.

For more explanations on the SoS certificate please refer to this website: The Sum of Squares Method.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.