Abstract
We consider nonnegative functions on abelian groups that are sparse with respect to the Fourier basis. We establish combinatorial conditions on subsets S and T of Fourier basis elements under which nonnegative functions with Fourier support S are sums of squares of functions with Fourier support T. Our combinatorial condition involves constructing a chordal cover of an associated Cayley Graph. Our result relies on two main ingredients: the decomposition of sparse positive semidefinite matrices with a chordal sparsity pattern, as well as a simple but key observation exploiting the structure of the Fourier basis elements of G.
We apply our general result to two examples. First, in the case where G = Z_2^n, we prove that any nonnegative quadratic form in n binary variables is a sum of squares of functions of degree at most ⌈n/2⌉, establishing a conjecture of Laurent. Second, we consider nonnegative functions of degree d on ℤN (when d divides N). By constructing a particular chordal cover of the d-th power of the N-cycle, we prove that any such function is a sum of squares of functions with at most 3dlog(N/d) nonzero Fourier coefficients. Dually this shows that a certain cyclic polytope in R^(2d) with N vertices has a semidefinite representation of size 3dlog(N/d). Putting N=d^2 gives a family of polytopes with LP extension complexity Ω(d^2) and SDP extension complexity O(dlog(d)). To the best of our knowledge, this is the first explicit family of polytopes whose semidefinite extension complexity is provably smaller than their linear programming extension complexity.
Joint work with Hamza Fawzi and James Saunderson. Preprint available at http://arxiv.org/abs/1503.