  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 are based
on sums of squares (SOS) as nonnegativity certificates. In this article, we
initiate the analysis of optimization problems over the boolean hypercube via a
recent, alternative certificate called sums of nonnegative circuit polynomials
(SONC). We show that key results for SOS based certificates remain valid:
First, for polynomials, which are nonnegative over the $n$-variate boolean
hypercube with constraints of degree $d$ there exists a SONC certificate of
degree at most $n+d$. Second, if there exists a degree $d$ SONC certificate for
nonnegativity of a polynomial over the boolean hypercube, then there also
exists a short degree $d$ SONC certificate, that includes at most $n^{O(d)}$
nonnegative circuit polynomials.
