Optimization Over the Boolean Hypercube Via Sums of Nonnegative Circuit Polynomials
Optimization Over the Boolean Hypercube Via Sums of Nonnegative Circuit Polynomials
Abstract Various key problems from theoretical computer science can be expressed as polynomial optimization problems over the boolean hypercube. One particularly successful way to prove complexity bounds for these types of problems is based on sums of squares (SOS) as nonnegativity certificates. In this article, we initiate optimization problems over …