Georgia Institute of Technology College of Sciences

We consider functions on finite abelian groups that are nonnegative and also sparse in the Fourier basis. We investigate conditions under which such functions admit sparse sum-of-certificates certificates of nonnegativity, i.e., certificates where the functions in the sum of squares decomposition have a small common sparsity pattern. Our conditions are purely combinatorial in nature, and are based on finding particularly nice chordal covers of a certain Cayley graph. These techniques allow us to show that any nonnegative quadratic function in binary variables is a sum of squares of functions of degree at mostceil(n/2), resolving a conjecture of Laurent. After discussing the connection with semidefinite programming lifts of polytopes, we also see how our techniques provide an example of separation between sizes ofsemidefinite programming lifts and linear programming lifts. This is joint work with James Saunderson and Pablo Parrilo.