1
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.