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 $2$ pseudo-distribution $\mu$ which has a negative pseudo-expectation with a non-negative objective function i.e $\mathbb{E}_\mu [f] <0$. This means that the degree $2$ SOS relaxation of the optimization problem $min_{x \in \{-1,1\}^n} f(x)$ will not be able to hit the correct minimum. (...alternatively one could say that this pair $(\mu,f)$ forms an integrality gap instance for this SOS relaxation at degree $2$...)

Now a hope to get out of this problem would be if one can show that for some degree $d >2$ this particular $\mu$ is no more in the feasible set of degree $d$ pseudo-distributions. Lets say that one wants to show that at $d=4$ this problem gets cured. I think that would be tantamount to showing that all degree $4$ pseudo-distributions have a non-negative inner product with this $\mu$ (inner product as defined in the first line)

  • What is the method (even if exponential time!) to show such a thing?


Your Answer

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