# About the SOS degree of a function and optimization algorithms for the function

Given a non-negative function on the hypercube $$f : \{0,1\}^n \rightarrow \mathbb{R}_{\geq 0}$$ one says that it is of "SOS-degree" of $$d$$ (denoted as $$deg_{SOS}(f) =d$$) if $$d$$ is the minimum $$k$$ such that one can find some finite number (say $$p$$) of polynomials on the hypercube $$g_i : \{0,1\}^n \rightarrow \mathbb{R}$$ ($$i=1,..,p$$) such that $$deg(g_i) \leq k/2$$ and $$f = \sum_{i=1}^p g_i^2(x)$$

• Given a function $$f$$ do we know anything about the hardness of computing its $$deg_{SOS}(f)$$ ? What is the fastest algorithm or approximation known for it?

• What does it mean in the bigger picture if it turns out that $$deg_{SOS}(f)$$ is large say $$O(n)$$ ? Does this immediately imply that the minimum running time required for an algorithm to get any constant fraction approximation of $$max(f)$$ or $$argmax(f)$$ is going to be exponential time?

I feel something like this should be true but I can't see such a thing being clearly written out..

Given any $$f : \{0,1\}^n \rightarrow \mathbb{R}_{\geq 0}$$ we can always write it as a SOS, $$f = \sum_{v \in \{0,1\}^n} f(v) i^2_v$$ where $$i_v : \{0,1\}^n \rightarrow \mathbb{R}_{\geq 0}$$ is the characteristic function of the vertex $$v \in \{0,1\}^n$$ as in $$i_v(w) = \delta_{vw}$$. Like for the vertex say $$(0,1,0)$$ one can choose its corresponding $$i = (1 - x_1)x_2(1-x_3)$$.

(Is there any name for these "i" functions?)

Hence we have trivially, $$deg_{SOS}(f) \leq n$$