arXiv:1802.10004v1 [cs.DS] 27 Feb 2018

OPTIMIZATION OVER THE BOOLEAN HYPERCUBE VIA SUMS OF
NONNEGATIVE CIRCUIT POLYNOMIALS
MAREIKE DRESSLER, ADAM KURPISZ, AND TIMO DE WOLFF
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 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 nOpdq nonnegative circuit polynomials.

1. Introduction
An optimization problem over a boolean hypercube is an n-variate (constrained) polynomial optimization problem where the feasibility set is restricted to the vertices of an
n-dimensional hypercube
(1.1)

min f pxq,
subject to p1 pxq, . . . , pm pxq ě 0,
x P tai , bi un ,
f, p1 , . . . , pm P Rrxs.

The formulation (1.1) captures a class of optimization problems, that belong to the core
of theoretical computer science. However, it is known that solving the above formulation
is NP-hard in general, since one can easily cast, e.g., the Independent Set problem in
this framework.
One of the most promising approaches in constructing efficient algorithms is the sum of
squares (SOS) hierarchy [GV01, Nes00, Par00, Sho87], also known as Lasserre relaxation
[Las01]. The method is based on a Positivstellensatz result [Put93] saying that the polynomial f , which is nonnegative over the feasibility set given in (1.1), can be expressed as
a sum of squares times the constraints defining the set. Bounding a maximum degree of a
polynomial used in a representation of f provides a family of algorithms parametrized by
2010 Mathematics Subject Classification. 14P10, 68Q25, 90C09; ACM Subject Classification: G.1.6
Convex programming, Nonlinear programming.
Key words and phrases. Certificate, hypercube optimization, nonnegativity, sums of nonnegative circuit polynomials, sums of squares.
1

2

MAREIKE DRESSLER, ADAM KURPISZ, AND TIMO DE WOLFF

an integer d. Finding a degree d SOS certificate for nonnegativity of f can be performed
by solving a semidefinite programming (SDP) formulation of size nOpdq . Finally, for every
(feasible) n-variate unconstrained hypercube optimization problem there exists a degree
2n SOS certificate.
On the one hand, the SOS algorithm provide the best available approximation algorithms for a wide variety of optimization problems. For example, the degree 2 SOS for
the Independent Set problem implies the Lovász θ-function [Lov79] and gives the
Goemans-Williamson relaxation [GW95] for the Max Cut problem. The ARV algorithm
of the Sparsest Cut [ARV09] problem can be captured by SOS of degree 6. Finally,
the subexponential time algorithm for Unique Games [ABS10] is implied by a SOS of
sublinear degree [BRS11, GS11]. More recently, it has been shown that Op1q degree SOS
is equivalent in power to any polynomial size SDP extended formulation in approximating maximum constraint satisfaction problems [LRS15]. Other applications of the SOS
method for combinatorial optimization can be found in [BRS11, BCG09, Chl07, CS08,
CGM13, dlVKM07, GS11, Mas17, MM09, RT12]. For a more detailed overview on the
use of SOS in approximation algorithms, see the surveys [CT, Lau03a, Lau09a].
On the other hand, it is known that the SOS algorithm admits certain weaknesses. First,
for some hypercube optimization problems the SOS algorithm performs much worse than
other known methods. Grigoriev in [Gri01] shows that a Ωpnq
degree SOS certificate is
ř
needed to detect that the Knapsack instance tx P r0, 1sn : ni“1 xi “ tn{2u`1{2u contains
no integer point. Simpler proofs can be found in [GHP02, Lau03b, KLM16]. Other SOS
degree lower bounds for Knapsack problems appeared in [Che07, KLM17a]. Another
example is the problem of scheduling unit size jobs on a single machine to minimize the
number of late jobs.
? The problem is solvable in polynomial time using the Moore-Hodgson
algorithm; an Ωp nq degree SOS algorithm, however, still attains an unbounded integrality gap [KLM17b]. For other important SOS limitations see e.g. [MPW15, BHK` 16].
Second, it remains open if finding a degree d SOS certificate can be performed in time
nOpdq . Indeed, as noted in the recent paper by O’Donnell [O’D17] and further discussed
by Raghavendra and Weitz in [RW17] it is not obviously true that the search can be done
so efficiently. Namely, even if a small degree SOS certificate exists, the polynomials in
the certificate do not have necessarily small coefficients. O’Donnell in [O’D17] gives an
example of a polynomial optimization problem that admits a degree 2 SOS certificate, but
every degree 2 SOS certificate for this problem has exponential bit complexity. Moreover,
in [RW17] the example is modified and cast into a hypercube optimization problem again
having a degree 2 SOS certificate, which,
however, has super-polynomial bit complexity
?
for certificates up to the degree Op nq. For small d, this excludes the possibility that
known optimization tools used for solving SDP problems like the ellipsoid method [Kha80,
GLS88] are able to find a degree d certificates in time nOpdq for optimization problems of
the form (1.1). The above arguments motivate the search of new methods for solving
hypercube optimization problems efficiently.
In this article, we initiate an analysis of hypercube optimization problems of the form
(1.1) via sums of nonnegative circuit polynomials (SONC). SONCs are a nonnegativity

OPTIMIZATION OVER THE BOOLEAN HYPERCUBE VIA SONCS

3

certificate introduced recently by Iliman and the third author [IdW16], which are independent of sums of squares; see Definition 2.1 and Theorem 2.4 for further details. Similarly
as Lasserre relaxation for SOS, a Schmüdgen-like Positivstellensatz yields a converging
hierarchy of lower bounds for polynomial optimization problems with compact constraint
set; see [DIdW17, Theorem 4.8] and Theorem 2.5. These bounds can be computed via a
convex optimization program called relative entropy programming (REP) [DIdW17, Theorem 5.3]. Our main question in this article is:
Can SONC certificates be an alternative for SOS methods for optimization
problems over the hypercube?
We answer this question affirmatively in the sense that we prove SONC complexity bounds
for (1.1) analogous to the SOS bounds mentioned above. More specifically, we show:
(1) For every polynomial which is nonnegative over an n-variate hypercube with constraints of degree at most d there exists a SONC certificate of nonnegativity of
degree at most n ` d; see Theorem 4.7 and Corollary 4.8.
(2) If a polynomial f admits a degree d SONC certificate of nonnegativity over an
n-variate hypercube, then the polynomial f admits also a short degree d SONC
certificate that includes at most nOpdq nonnegative circuit polynomials; see Theorem 4.9.
For a discussion and remaining open problems, to turn these results into an efficient
algorithms, see Section 2.3 and the end of Section 4.2.
Furthermore, we show some structural properties of SONCs:
(1) We give a simple, constructive example showing that the SONC cone is not closed
under multiplication. Subsequently we use this construction to show that the
SONC cone is neither closed under taking affine transformations of variables, see
Lemma 3.1 and Corollary 3.2.
(2) We address an open problem raised in [DIdW17] asking whether the Schmüdgenlike Positivstellensatz for SONCs (Theorem 2.5) can be improved to an equivalent
of Putinar’s Positivstellensatz [Put93]. We answer this question negatively by
showing an explicit hypercube optimization example, which provably does not
admit a Putinar representation for SONCs; see Theorem 5.1 and the discussion
afterwards.
Our article is organized as follows: In Section 2 we introduce the necessary background
about SONCs. In Section 3 we show that the SONC cone is closed neither under multiplication nor under affine transformations. In Section 4 we provide our two main results
regarding the degree bounds for SONC certificates over the hypercube. In Section 5 we
prove the non-existence of an equivalent of Putinar’s Positivstellensatz for SONCs and
discuss this result.
Acknowledgements. AK was supported by the Swiss National Science Foundation
project PZ00P2 174117 “Theory and Applications of Linear and Semidefinite Relaxations
for Combinatorial Optimization Problems”. TdW was supported by the DFG grant WO
2206/1-1. This article was finalized while TdW was hosted by the Institut Mittag-Leffler.
We thank the institute for its hospitality.

4

MAREIKE DRESSLER, ADAM KURPISZ, AND TIMO DE WOLFF

2. Preliminaries
In this section we collect basic notions and statements on sums of nonnegative circuit
polynomials (SONC).
Throughout the paper, we use bold letters for vectors, e.g., x “ px1 , . . . , xn q P Rn . Let
N˚ “ Nzt0u and Rě0 (Rą0 ) be the set of nonnegative (positive) real numbers. Furthermore
let Rrxs “ Rrx1 , . . . , xn s be the ring of real n-variate polynomials and the set of all nvariate polynomials of degree less than or equal to 2d is denoted by`Rrxs
˘ n,2d . We denote
řd
n
by
k“0 k is abbreviated by
` n rns
˘ the set t1, . . . , nu and the sum of binomial coefficients
n
.
Let
e
,
.
.
.
,
e
denote
the
canonical
basis
vectors
in
R
.
1
n
ďd

2.1. Sums of Nonnegative Circuit Polynomials. Let A Ă Nn be a finite set. In
what follows,
we consider polynomials f P Rrxs supported on A. Thus, f is of the form
ř
f pxq “ αPA fα xα with fα P R and xα “ xα1 1 ¨ ¨ ¨ xαnn . A lattice point is called even if it is
in p2Nqn and a term fα xα is called a monomial square if fα ą 0 and α even. We denote
by Newpf q “ convtα P Nn : fα ‰ 0u the Newton polytope of f .
Initially, we introduce the foundation of SONC polynomials, namely circuit polynomials;
see also [IdW16]:
Definition 2.1. A polynomial f P Rrxs is called a circuit polynomial if it is of the form
r
ÿ
(2.1)
f pxq :“
fαpjq xαpjq ` fβ xβ ,
j“0

with r ď n, exponents αpjq, β P A, and coefficients fαpjq P Rą0 , fβ P R, such that the
following conditions hold:
(C1): Newpf q is a simplex with even vertices αp0q, αp1q, . . . , αprq.
(C2): The exponent β is in the strict interior of Newpf q. Hence, there exist unique
barycentric coordinates λj relative to the vertices αpjq with j “ 0, . . . , r satisfying
r
r
ÿ
ÿ
β “
λj αpjq with λj ą 0 and
λj “ 1.
j“0

j“0

We call the terms fαp0q xαp0q , . . . , fαprq xαprq the outer terms and fβ xβ the inner term of f .
For every circuit polynomial we define the corresponding circuit number as
˙
r ˆ
ź
fαpjq λj
(2.2)
.
Θf :“
λ
j
j“0
7

The first fundamental statement about circuit polynomials is that its nonnegativity is
determined by its circuit number Θf and fβ entirely:
Theorem 2.2 ([IdW16], Theorem 3.8). Let f be a circuit polynomial with inner term fβ xβ
and let Θf be the corresponding circuit number, as defined in (2.2). Then the following
statements are equivalent:

OPTIMIZATION OVER THE BOOLEAN HYPERCUBE VIA SONCS

(1) f is nonnegative.
(2) |fβ | ď Θf and β R p2Nqn

or

5

fβ ě ´Θf and β P p2Nqn .

Therefore, expressing a polynomial as a sum of nonnegative circuit polynomials (SONC)
is a certificate for the polynomials nonnegativity.
Definition 2.3. We define for every n, d P N˚ the set of sums of nonnegative circuit
polynomials (SONC) in n variables of degree 2d as
+
#
k
ÿ
p is a nonnegative circuit polynomial,
Cn,2d :“ f P Rrxsn,2d : f “
µ i pi , i
µi ě 0, k P N˚
i“1

7

We denote by SONC both the set of SONC polynomials and the property of a polynomial to be a sum of nonnegative circuit polynomials.
In what follows let Pn,2d be the cone of nonnegative n-variate polynomials of degree
at most 2d and Σn,2d be the corresponding cone of sums of squares respectively. An
important observation is, that SONC polynomials form a convex cone independent of the
SOS cone:
Theorem 2.4 ([IdW16], Proposition 7.2). Cn,2d is a convex cone satisfying:
(1) Cn,2d Ď Pn,2d for all n, d P N˚ ,
(2) Cn,2d Ď Σn,2d if and only if pn, 2dq P tp1, 2dq, pn, 2q, p2, 4qu,
(3) Σn,2d Ę Cn,2d for all pn, 2dq with 2d ě 6.
For further details about the SONC cone see [dW15, IdW16, DIdW17].
2.2. SONC Certificates over a Constrained Set. In [DIdW17, Theorem 4.8], Iliman,
the first, and the third author showed that for an arbitrary real polynomial which is strictly
positive on a compact, basic closed semialgebraic set K there exists a SONC certificate
of nonnegativity. Hereinafter we recall this result.
We assume that K is given by polynomial inequalities gi pxq ě 0 for i “ 1, . . . , s and is
compact. For technical reason we add 2n redundant box constraints lj pxq :“ N ˘xj ě 0 for
some sufficiently large N P N, which always exists due to our assumption of compactness
of K; see [DIdW17] for further details. Hence, we have
(2.3)

K :“ tx P Rn : gi pxq ě 0 for i P rss and lj pxq ě 0 for j P r2nsu.

In what follows we consider polynomials H pqq pxq defined as products of at most q P N˚ of
the polynomials gi , lj and 1, i.e.,
(2.4)

H

pqq

pxq :“

q
ź

k“1

hk pxq,

where hk P t1, g1 , . . . , gs , l1 , . . . , l2n u. Now we can state:

6

MAREIKE DRESSLER, ADAM KURPISZ, AND TIMO DE WOLFF

Theorem 2.5. Let f, g1 , . . . , gs P Rrxs be real polynomials and K be a compact, basic
closed semialgebraic set as in (2.3). If f ą 0 on K then there exist d, q P N˚ such that we
have an explicit representation of f of the following form:
ÿ
spxqH pqq pxq,
f pxq “
finite

where the spxq are contained in Cn,2d and every H pqq pxq is a product as in (2.4).

The central object of interest is the smallest value of d and q that allows f a decomposition as in Theorem 2.5. This motivates the following definition of a degree d SONC
certificate.
Definition 2.6. Let f P Rrxs such that f is positive on the set K given in (2.3). Then f
has a degree d SONC certificate if it admits for some q P N˚ the following decomposition:
ÿ
spxqH pqq pxq,
f pxq “
finite

where the spxq are SONCs, the H pqq pxq are products as in (2.4), and
¸
˜
ÿ
spxqH pqq pxq ď d.
deg
finite

7

2.3. The Complexity of Finding a Degree d SONC Certificate. One can decide
nonnegativity for a single given circuit polynomial by solving a system of linear equations. This is due to Theorem 2.2 and the fact that the λj are unique (and thus trivially
nonnegative), since the αpjq are affinely independent by construction.
For finding a degree d SONC certificate, there are two main bottlenecks that might effect
its complexity. The first one is to guarantee the existence of a sufficiently short degree
d SONC certificate. If the first bottleneck is resolved, then a second one might occur:
even if the existence of a short degree d SONC certificate is guaranteed, then it is not
clear a priori, whether one can search through the space of n-variate circuit polynomials
of degree at most d efficiently, in order to find such a short certificate.
Regarding the first bottleneck, given the fact that a polynomial f admits a degree d
SONC certificate, it is open whether there also exists a degree d certificate which consists
of a bounded (ideally nOpdq ) number of components.
The answer to the equivalent question for the SOS degree d certificates follows from
the fact that a polynomial is SOS if and only if the corresponding matrix of coefficients
of size nOpdq , called the Gram matrix, is positive semidefinite. Since every real, symmetric
matrix M that is positive semidefinite admits a decomposition M “ V V J , this yields an
explicit SOS certificate including at most nOpdq polynomials squared. For more details we
refer the reader to the excellent lecture notes in [BS16].
In this paper we resolve the first bottleneck regarding the existence of short SONC
certificates affirmatively. Namely, we show that one can always restrict oneself to SONC
certificates including at most nOpdq nonnegative circuit polynomials, see Section 4.2 for
further details.

OPTIMIZATION OVER THE BOOLEAN HYPERCUBE VIA SONCS

7

Figure 1. The Newton polytope and the support set of rpx1 , xk q with the
supports of p1 and p2 in blue ovals.
3. Properties of the SONC cone
In this section we show that the SONC cone is neither closed under multiplication nor
under affine transformations. First, we give a constructive proof for the fact that the
SONC cone is not closed under multiplication, which is simpler than the initial proof of
this fact in [DIdW17, Lemma 4.1]. Second, we use our construction to show that the
SONC cone is not closed under affine transformation of variables.
Lemma 3.1. For every d ě 2, n P N˚ the SONC cone Cn,d is not closed under multiplication in the following sense: if p1 , p2 P Cn,d , then p1 ¨ p2 R Cn,2d in general.
Proof. For every d “ 2n, n P N˚ we construct two SONC polynomials p1 , p2 P Cn,d such
that the product p1 p2 is an n variate, degree 2d polynomial that is not inside Cn,2d .
Let n “ 2. We construct the following two polynomials p1 , p2 P Rrx1 , x2 s:
p1 px1 , x2 q :“ p1 ´ x1 q2 ,

p2 px1 , x2 q :“ p1 ´ x2 q2 .

First, observe that p1 , p2 are nonnegative circuit polynomials, since, in both cases, λ1 “
λ2 “ 1{2, fαp1q “ fαp2q “ 1, and fβ “ ´2, thus 2 “ Θf ě |fβ |.
Now consider the polynomial rpx1 , x2 q “ p1 p2 “ pp1 ´ x1 qp1 ´ x2 qq2 . We show that
this polynomial, even though it is nonnegative, is not a SONC polynomial. Note that
rpx1 , x2 q “ 1 ´ 2x1 ´ 2x2 ` 4x1 x2 ` x21 ` x22 ´ 2x21 x2 ´ 2x1 x22 ` x21 x22 ; the support of r is
shown in Figure 1. Assume that r P C2,4 , i.e., r has a SONC decomposition. This implies
that the term ´2x1 has to be an inner term of some nonnegative circuit polynomial r1 in
this representation. Such a circuit polynomial necessarily has the terms 1 and x21 as outer
terms, that is,
r1 px1 q “ p1 px1 , x2 q “ 1 ` x21 ´ 2x1
Since Θr1 “ 2 the polynomial r1 is indeed nonnegative and, in addition, we cannot choose
a smaller constant term to construct r1 . Next, also the term ´2x2 has to be an inner term
of some nonnegative circuit polynomial r2 . Since this term again is on the boundary of
Newprq the only option for such an r2 is: r2 px2 q “ p2 px1 , x2 q “ 1 ` x22 ´ 2x2 . However, the

8

MAREIKE DRESSLER, ADAM KURPISZ, AND TIMO DE WOLFF

term 1 has been already used in the above polynomial r1 , which leads to a contradiction,
i.e., r R C2,4 . Since Cn,2d Ď Cn`1,2d , the general statement follows.


Hereinafter we show another operation, which behaves differently for SONC than it
does for SOS: Similarly as in the case of multiplications, affine transformations also do not
preserve the SONC structure. This observation is important for possible degree bounds
on SONC certificates, when considering optimization problems over distinct descriptions
of the hypercube.
Corollary 3.2. For every d ě 4, n P N˚ the SONC cone Cn,d is not closed under affine
transformation of variables.
Proof. Consider the polynomial f px1 , x2 q “ x21 x22 . Clearly, the polynomial f is a nonnegative circuit polynomial since it is a monomial square, hence f P Cn,d. Now consider the
following affine transformation of the variables x1 and x2 :
x1 Ñ 1 ´ x1 ,

x2 Ñ 1 ´ x2 .

After applying the transformation the polynomial f equals the polynomial p1 p2 from the
proof of Lemma 3.1 and thus is not inside Cn,d.

4. An Upper Bound on the Degree of SONC Certificates over the
Hypercube
In the previous section we showed that the SONC cone is not closed under taking an
affine transformation of variables, Corollary 3.2. Thus, if a polynomial f admits a degree
d SONC certificate proving that it is nonnegative on a given compact semialgebraic set
K, then it is a priori not clear whether a polynomial g, obtained from f via an affine
transformation of variables, admits a degree d SONC certificate of nonnegativity on K,
too. The degree needed to prove nonnegativity of g might be much larger than d according
to the argumentation in the proof of Corollary 3.2.
In this section we prove that every n-variate polynomial which is nonnegative over
the boolean hypercube has a degree n SONC certificate. Moreover, if the hypercube is
additionally constrained with some polynomials of degree at most d, then the nonnegative
polynomial over such a set has degree n ` d SONC certificate. We show this fact for all
hypercubes tai , bi un ; see Theorem 4.3 for further details.
Formally, we consider the following setting: We investigate real multivariate polynomials in Rrxs. For j P rns, and aj , bj P R, such that aj ă bj let
gj pxq :“ pxj ´ aj qpxj ´ bj q

be a quadratic polynomial withśtwo distinct real roots. Let H Ă Rn denote the ndimensional hypercube given by nj“1 taj , bj u. Moreover, let
P :“ tp1 , . . . , pm : pi P Rrxs, i P rmsu

be a set of polynomials, which we consider as constraints pi pxq ě 0 with degppi pxqq ď d
for all i P rns as follows. We define
HP :“ tx P Rn : gj pxq “ 0, j P rns, ppxq ě 0, p P Pu

OPTIMIZATION OVER THE BOOLEAN HYPERCUBE VIA SONCS

9

as the n-dimensional hypercube H constrained by polynomial inequalities given by P.
Throughout the paper we assume that |P| “ polypnq, i.e. the size of the constraint
set P is polynomial in n. This is usually the case, since otherwise the problem gets less
tractable from the optimization point of view.
As a first step, we introduce a Kronecker function:
Definition 4.1. For every v P H the function
ˆ
˙
˙
ˆ
ź
ź
xj ´ aj
´xj ` bj
(4.1)
¨
δv pxq :“
bj ´ aj
bj ´ aj
jPrns: v “b
jPrns: v “a
j

j

j

j

is called the Kronecker delta (function) of the vector v.

Next we show that the term “Kronecker delta” is justified, i.e., we show that for every
v P H the function δv pxq takes the value zero for all x P H except for x “ v where it
takes the value one.
Lemma 4.2. For every v P H it holds that:
#
0,
for every x P Hztvu,
δv pxq “
1,
for x “ v.
Proof. On the one hand, if x P Hztvu, then there exists an index k such that xk ‰ vk .
This implies that there exists at least one multiplicative factor in δv which attains the
value zero due to (4.1). On the other hand if x “ v then we have
ˆ
ˆ
˙
˙
ź
ź
´aj ` bj
bj ´ aj
δv pxq “
“ 1.
b
´
a
b
´
a
j
j
j
j
jPrns: v “a
jPrns: v “b
j

j

j

j



The main result of this section is the following theorem.
Theorem 4.3. Let f pxq P Rrxsn,n. Then f pxq ě 0 for every x P HP if and only if f has
the following representation:
(4.2)

f pxq “

ÿ

vPHP

cv δv pxq `

ÿ

cv δv pxqpv pxq `

vPHzHP

where s1 , . . . , s2n P Cn,n´2, cv P Rě0 and pv P P.

n
ÿ

j“1

sj pxqgj pxq `

n
ÿ

sn`j pxqp´gj pxqq,

j“1

Since we are interested in optimization on the boolean hypercube H, we assume without
loss of generality that the polynomial f considered in Theorem 4.3 has degree at most
n. Indeed, it f has degree bigger than n, one can efficiently reduce the degree of f by
applying iteratively the polynomial division with respect to polynomials gj with j P rns.
The remainder of the division process is a polynomial with degree at most n that agrees
with f on all the vertices of H.
We begin with proving the easy direction of the equivalence stated in Theorem 4.3.
Lemma 4.4. If f admits a decomposition of the form (4.2), then f pxq is nonnegative for
all x P HP .

10

MAREIKE DRESSLER, ADAM KURPISZ, AND TIMO DE WOLFF

Proof. The coefficients cv are nonnegative, all sj pxq are SONC and hence nonnegative on
Rn . We have ˘gj pxq ě 0 for all x P H, and for all choices of v P H we have pv pxq ě 0 for
all x P HP , and δv pxq P t0, 1u for all x P H. Thus, the right hand side of (4.2) is a sum
of positive terms for all x P HP .


We postpone the rest of the proof of Theorem 4.3 to the end of the section. Now, we
state an result about the presentation of the Kronecker delta function δv .
Lemma 4.5. For every v P H the Kronecker delta function can be written as
2n
ÿ
pnq
δv “
sj H j ,
j“1

pnq

for s1 , . . . , s2n P Rě0 and every Hj given as in (2.4) with q “ n and K given by the
hypercube constraints g1 , . . . , gn and l1 , . . . , l2n .
Proof. First note that the function δv can be rewritten as
2n
ź
ź
ź
1
δv pxq “
p´xj ` bj q
pxj ´ aj q ,
b ´ aj jPrns: v “a
j“1 j
jPrns:
v
“b
j
j
j
j
śn
1
where j“1 bj ´aj P Rě0 . Now, the proof follows just by noting that for every j P rns both
inequalities ´xj ` bj ě 0 and xj ´ aj ě 0 are in K.

The following statement is well-known in similar variations; see e.g. [BS14, Lemma 2.2
and its proof]. For clarity, we provide an own proof here.
ř
Proposition 4.6. Let f P Rrxsn,2d be a polynomial vanishing on H. Then f “ nj“1 pj gj
for some polynomials pj P Rrxsn,2d´2 .

Proof. Let J :“ xg1 , . . . , gn y be the ideal generated by the gj ’s. Let VpJ q denote the affine
variety corresponding to Jś
, IpVpJ qq denote its radical ideal, and let IpHq denote the
ideal of H. It follows from nj“1 gj P J that VpJ q Ď H and hence IpHq Ď IpVpJ qq “ J .
The last equality holds since J itself is a radical ideal. This results from Seidenberg’s
Lemma; see [KR00, Proposition 3.7.15] by means of the following observations. The affine
variety VpJ q consists exactly of the points defining H, therefore we know that J is a zerodimensional ideal. Furthermore, for every j P rns the polynomials
ř gj satisfy gj P J XRrxj s
and gcdpgj , gj1 q “ 1. Thus, every f P IpHq is of the form f “ nj“1 pj gj .
Moreover G :“ tg1 , . . . , gn u is a Gröbner basis for J with respect to the graded lexicographic order ăglex . This follows from Buchberger’s Criterion, which says that G is a
Gröbner basis for J if and only if for all pairs i ‰ j the remainder on the division of
the S-polynomials Spgi , gj q by G with respect to ăglex is zero. Consider an arbitrary pair
gi , gj with i ą j. Then the corresponding S-polynomial is given by
Spgi , gj q “ paj ` bj qx2i xj ´ pai ` bi qxi x2j ´ aj bj x2i ` ai bi x2j .

Applying polynomial division with respect to ăglex yields the remainder 0 and hence G is
a Gröbner basis for J with respect to ăglex . Therefore, we conclude that if f P Rrxsn,2d ,
then degppj q ď 2d ´ 2.


OPTIMIZATION OVER THE BOOLEAN HYPERCUBE VIA SONCS

11

For an introduction to Gröbner bases see for example [CLO15].
Theorem 4.7. Let d P N and f PřRrxsn,2d`2 ř
such that f vanishes on H. Then there exist
s1 , . . . , s2n P Cn,2d such that f “ nj“1 sj gj ` nj“1 sn`j p´gj q.
ř
Proof. By Proposition 4.6 we know that f “ nj“1 pj gj for some polynomials pj of degree
ř
ď 2d. Hence, it is sufficient to show that every single term pj gj is of the form nj“1 sj gj ´
řℓ
řn
i“1 aji mji where every aji P R and
j“1 sn`j gj for some s1 , . . . , s2n P Cn,2d . Let pj “
every mji is a single monomial. We show that pj gj has the desired form by investigating
an arbitrary individual term aji mji gj .
Case 1: Assume the exponent of mji is contained in p2Nqn . If aji mji is a monomial
square, then aji mji is a circuit polynomial. If aji ă 0, then ´aji mji is a monomial square.
In both cases we obtain a representation sji p˘gji q, where sji P Cn,2d .
Case 2: Assume the the exponent β of mji contains odd numbers. Without loss
of generality, assume that β “ pβ1 , . . . , βk , βk`1 , . . . , βn q such that the first k entries
are odd and the remaining n ´ k entries are even. We construct a SONC polynomial
sji “ aαp1q xαp1q ` aαp2q xαp2q ` aji xβ such that
(4.3)
(4.4)

αp1q “ β `
|aji | ď

rk{2s
ÿ
j“1

ej ´

k
ÿ

ej ,

j“rk{2s`1

a
2aαp1q aαp2q .

αp2q “ β ´

rk{2s
ÿ
j“1

ej `

k
ÿ

ej ,

j“rk{2s`1

By the construction (4.3) αp1q, αp2q P p2Nqn and β “ 1{2pαp1q ` αp2qq. Thus, sji is a
circuit polynomial and by (4.4) the coefficients
aαp1q , aαp2q are chosen large enough such
a
that |aji | is bound by the circuit number 2aαp1q aαp2q corresponding to sji . Thus, sji is
nonnegative by [IdW16, Theorem 1.1]. Thus, we obtain
aji mji gj “ sji gj ` paαp1q xαp1q ` aαp2q xαp2q qp´gj q,

where sji , aαp1q xαp1q , and aαp2q xαp2q are nonnegative circuit polynomials.
Degree: All involved nonnegative circuit polynomials are of degree at most 2d. In
Case 1 this follows by construction. In Case 2 we have for the circuit polynomial sji that
degpαp1qq, degpαp2qq “ degpβq if k is even, and degpαp1qq “ degpβq ` 1, degpαp2qq “
degpβq if k is odd. Since β is an exponent of the polynomial f , we know that degpβq ď 2d.
If k is odd, however, then
degpβq “

k
ÿ

j“1

j on `
looβ
mo

odd number

n
ÿ

j“k`1

j on ,
looβ
mo

even number

i.e., degpβq is a sum of k many odd numbers, with k being odd, plus a sum of even
numbers. Thus, degpβq has to be an odd number and hence degpβq ă 2d. Therefore, all
degrees of terms in sji are bounded by 2d and thus sji P Cn,2d .
Conclusion: We have that
ℓj
ℓj
n
n ÿ
n ÿ
ÿ
ÿ
ÿ
f “
pj g j “
aji mji gj “
sji gj .
j“1

j“1 i“1

j“1 i“1

12

MAREIKE DRESSLER, ADAM KURPISZ, AND TIMO DE WOLFF

By Cases 1 and 2 and the degree argument, we have sji P Cn,2d for every i, j and by
ř ℓj
defining sj “ i“1
sji P Cn,2d we obtain the desired representation of f .

4.1. Proof of Theorem 4.3. In this section we combine the results of this section and
finish the proof of Theorem 4.3.

Due to Lemma 4.4, it remains to show that f pxq admits a decomposition of the form
(4.2) if f pxq ě 0 for every x P HP .
Hence, when restricted to the hypercube H, the polynomial f can be represented in the
following way:
ÿ
ÿ
δv pxq ` f pxq
δv pxq
for all x P H
f pxq “ f pxq
vPHP

“

ÿ

vPHP

vPHzHP

δv pxqf pvq `

ÿ

vPHzHP

δv pxqf pvq

for all x P H,

where the last equality follows by Lemma 4.2 .
Note that there might exist a vector v P HzHP such that f attains a negative value at
v. If f pvq ă 0, then let pv P P be one of the polynomials among the constraints satisfying
pv pvq ă 0. Otherwise, let pv “ 1. Since by Lemma 4.2 we have δv pxqpv pxq “ δv pxqpv pvq
for every v, x P H, we can now write:
f pxq “

ÿ

vPHP

δv pxqf pvq `

ÿ

vPHzHP

δv pxqpv pxq

f pvq
pv pvq

for all x P H.

ř
ř
has degree at
Thus, the polynomial f pxq ´ vPHP δv pxqf pvq ´ vPHzHP δv pxqpv pxq pfvpvq
pvq
most n ` d and vanishes on H. By Theorem 4.7 we finally get
f pxq “

n
ÿ

j“1

sj pxqgj pxq `

n
ÿ

j“1

sn`j pxqp´gj pxqq `

ÿ

vPHP

δv pxqf pvq `

ÿ

vPHzHP

δv pxqpv pxq

f pvq
,
pv pvq

for some s1 , . . . , s2n P Cn,n´2 and pv P P. This, together with Lemma 4.5, finishes proof
together with.

Corollary 4.8. For every polynomial f which is nonnegative over the boolean hypercube
constrained with polynomial inequalities of degree at most d there exists a degree n ` d
SONC certificate.
Proof. The argument follows directly from Theorem 4.3 by noting that the right hand
side of (4.2) is a SONC certificate of degree n ` d (see the Definition 2.6).

4.2. Degree d SONC Certificates. In this section we show that if a polynomial f
admits a degree d SONC certificate, then f also admits a short degree d certificate that
involves at most nOpdq terms. We conclude the section with a discussion regarding the
time complexity of finding a degree d SONC certificate.

OPTIMIZATION OVER THE BOOLEAN HYPERCUBE VIA SONCS

13

Theorem 4.9. Let f be an n-variate polynomial, nonnegative on the constrained hypercube HP with |P| “ polypnq. Assume that there exists a degree d SONC certificate
for
`n˘
f , then there exists a degree d SONC certificate for f involving at most Op ďd q many
nonnegative circuit polynomials.
Proof. Since there exists a degree d SONC proof of the nonnegativity of f on HP we know
that
ÿ
pqq
f pxq “
sj H j ,
j

pqq

where the summation is finite, the sj ’s are SONCs, and every Hj is a product as defined
in (2.4).
Step 1: We analyze the terms sj . Since every sj is a SONC, we know that there exists
a representation
kj
ÿ
sj “ κj ¨
µij ¨ qij
i“1

ř kj

such that κj , µ1j , . . . , µkj j P Rą0 , i“1 µij “ 1, and the qij are nonnegative circuit polynomials. Since sj is of degree at most d, we know that Qj :“ tq1j , . . . , qkj j u is contained in
` ˘
Rn,d rxs, which is a real vector space of dimension n`d
. Since sj {κj is a convex combinad
` ˘
tion of the qij , i.e. in the convex hull of Qj , and dimpQj q ď n`d
, applying Carathéodory’s
d
Theorem,
`n`d˘see e.g. [Zie07], yields that sj {κj can be written as a convex combination of at
most d ` 1 many of the cij .
pqq
pqq
Step 2: We analyze the terms Hj . By definition of the HP and the terms Hj we
have
pqq
H j “ g j 1 ¨ ¨ ¨ g j s ¨ l r 1 ¨ ¨ ¨ lr t ¨ p ℓ 1 ¨ p ℓ v
with j1 , . . . , js P rns, r1 , . . . , rt P r2ns, and ℓ1 , . . . , ℓv P rms. Since the maximal degree of
`
˘
pqq
pqq
Hj is d, the number of different Hj ’s is bounded from above by n`2n`m
.
d
Conclusion: In summary, we obtain a representation:
f pxq “

q
pn`2n`m
d
ÿ
i“1

pqq

H j sj “

q
pn`2n`m
d
ÿ
i“1

pqq

Hj κj

pn`d
d
ÿq`1

µij cij

j“1

Since, as assumed m can bounded by polypnq, the total number of summands is
polypnqOpdq “ nOpdq , and we found a desired representation with at most nOpdq nonnegative
circuit polynomials of degree at most d.

The Theorem 4.9 states that when searching for a degree d SONC certificate it is
enough to restrict to certificates containing at most nOpdq nonnegative circuit polynomials.
Moreover, as proved in [DIdW17, Theorem 3.2] for a given set A Ď Nn , searching through
the space of degree d SONC certificates supported on set A can be computed via a
relative entropy program (REP) of size nOpdq . However, the above arguments do not
necessarily imply that that the search through the space of degree d SONC certificates
can be performed in time nOpdq . The difficulty is that one needs to restrict the configuration

14

MAREIKE DRESSLER, ADAM KURPISZ, AND TIMO DE WOLFF

space of n-variate degree d SONCs to a subset of order nOpdq to be able to formulate the
corresponding REP in time nOpdq . Since the current proof of Theorem 4.9 just guarantees
the existence of a short SONC certificate, it is currently not clear, how to search for a
short certificate efficiently. We leave this as an open problem.
5. There Exists No Equivalent to Putinar’s Positivstellensatz for
SONCs
In this section we address the open problem raised in [DIdW17] asking whether the
Theorem 2.5 can be strengthened by requiring q “ 1. Such a strengthening, for a positive polynomial over some basic closed semialgebraic set, would provide a SONC decomposition equivalent to Putinar’s Positivstellensatz for SOS; for background see e.g.,
[Lau09b, Put93]. We answer this question in a negative way. More precisely, we provide
a polynomial f which is strictly positive over the hypercube t˘1un such that there does
not exist a SONC decomposition of f for q “ 1. Moreover, we prove it not only for the
most natural choice of the box constraints, that is li “ 1 ˘ xi , but for a generic type of
box constraints of the form ℓi “ 1 ` ci ˘ xi with ci P Rě0 . We close the section with a
short discussion.
Let H “ t˘1un and consider the following set of polynomials parametrized by a natural
number a:
˙
n ˆ
ź
xi ` 1
fa pxq :“ pa ´ 1q
` 1.
2
i“1
ř
These polynomials satisfy fa peq “ a for the vector e “ ni“1 ei and fa pxq “ 1 for every
other x P Hzteu. We define for every d P N
+
#
ÿ
(
s ¨ h : s P Cn,2d , h P 1, ˘px2i ´ 1q, 1 ` ci ˘ xi : i P rns, ci P Rě0
Sd :“
finite

as the set of polynomials admitting a SONC decomposition over H given by Theorem 2.5
for q “ 1. The main result of this section is the following theorem.
Theorem 5.1. For every a ą

2n ´1
2n´2 ´1

we have fa R Sd for all d P N.

Before we prove this theorem, we show the following structural results. Note that
similar structural observations were already made for AGIforms by Reznick in [Rez89]
using a different notation.
Lemma 5.2. Every spxq P Cn,2d attains at most two different values on H “ t˘1un .
Moreover, if spxq attains two different values, then each value is attained for exactly the
half of the hypercube vertices.
Proof. By Definition 2.1 every nonnegative circuit polynomial is of the form:
spxq “

r
ÿ

j“0

fαpjq xαpjq ` fβ xβ .

OPTIMIZATION OVER THE BOOLEAN HYPERCUBE VIA SONCS

15

Note that for j “ 0, . . . , r, we have αpjq P p2Nqn . Hence when evaluated over
ř the hypercube x P H “ t˘1un , spxq can take only one of at most two different values rj“0 fαpjq ˘fβ .
If spxq attains two different values over H, then there has to exist a non empty subset
of
řr variables that have an odd entry in β. Let I Ď rns be this subset. Then spxq “
j“0 fαpjq pxq ´ fβ pxq, for x P H if and only if x has an odd number of ´1 entries in the
set I. The number of such vectors is equal to
2

n´|I|

|I|
ÿ

i“0,
i odd

2i “ 2n´|I|2|I|´1 “ 2n´1 .


Lemma 5.3. Every polynomial spxqℓi pxq, with s P Cn,2d and ℓi “ 1 ` ci ˘ xi being a box
constraint, attains at most four different values on H “ t˘1un . Moreover, each value is
attained for at least one forth of the hypercube vertices.
´ř
¯
r
Proof. By Lemma 5.2, spxq attains at most the two values
f
˘
f
β on H. Simij“0 αpjq
larly, ℓi pxq attains at most the two values´1 ` ci ˘ xi over H.
¯ Thus, a polynomial spxqℓi pxq
řr
attains at most the four different values
j“0 fαpjq ˘ fβ p1 ` ci ˘ xi q on H.
Let I be as in the proof of Lemma 5.2,ři.e., the subset of variables that have an odd
entry in β. If I “ H, then the first term rj“0 fαpjq ` fβ is constant over the hypercube
H, thus spxqℓi pxq takes two different values depending on the i-th entry of the vector.
Each value is attained for exactly half of the vectors.
If I ‰ H and i R I the claim holds since the value of the first term depends only on
the entries in I and the value of the second term depends on the i-th entry. Hence, the
polynomial spxqℓi pxq attains four values each on exactly one fourth of H vectors.
Finally, let I ‰ H and i P I. Partition the hypercube vertices into two sets depending
on the i-th entry. Each set has cardinality 2n´1. Consider the set with xi “ 1. For
the vectors in this set the second term
ř takes a constant value 2 ` c. Over this set the
polynomial s takes one of the values rj“0 fαpjq pxq ˘ fβ pxq, depending on whether x has
an odd or even number of ´1 entries in the set Izt´1u. In both cases the number of such
vectors is equal to
|I|´1
ÿ
n´|I|
2
2i “ 2n´|I| 2|I|´2 “ 2n´2 .
i“0,
i odd

The analysis for the case xi “ ´1 is analogous.



Now we can provide the proof of Theorem 5.1.
Proof. (Proof of Theorem 5.1)
Assume fa P Sd for some a P N and d P N. We prove that a has to be smaller or equal
2n ´1
than 2n´2
.
´1

16

MAREIKE DRESSLER, ADAM KURPISZ, AND TIMO DE WOLFF

Since fa P Sd we know that
fa pxq “ s0 pxq `

n
ÿ

i“1

si pxqℓi pxq `

n
ÿ

j“1

s̃j pxqpx2j ´ 1q ` s̃j`n pxqp1 ´ x2j q

with s0 , . . . , sn , s̃1 , . . . , s̃2n P Cn,2d . Since ˘px2j ´ 1q for j P rns vanishes over the hypercube
H, we can conclude
fa pxq “ s0 pxq `

(5.1)

n
ÿ

i“1

si pxqℓi pxq

for all x P H

for some s0 , s1 , . . . , sn P Cn,2d .
ř
Letřs0,k , and si,j be some nonnegative circuit polynomials such that s0 “ k s0,k , and
si “ j si,j . Thus, we get
˜
¸
n
ÿ
ÿÿ
ÿÿ ÿ
ÿ
s0 pxq `
si pxqℓi pxq
“
s0,k pxq `
si,j pxqℓi,j pxq
xPH

i“1

k xPH

ě

ÿ
k

2n´1 s0,k peq `
˜

ě 2n´2 s0 peq `
“ 2n´2 a

i j xPH
n ÿ
ÿ
n´2

2

i“1 j

n
ÿ

i“1

si peqℓi peq

si,j peqℓi,j peq

¸

where the first inequality comes directly from Lemma 5.2 and 5.3 and the last equality
from the fact that fa peq “ a.
On the other hand, by the properties of the function fa and the equality (5.1), we know
that
˜
¸
ÿ
ÿ
s0 pxq ` si pxqℓi pxq “ 2n ´ 1 ` a,
xPH

i

which makes the subsequent inequality a necessary requirement for fa P Sd :
a ď

2n ´ 1
.
2n´2 ´ 1



Speaking from a broader perspective, we interpret Theorem 5.1 as an indication that
the real algebraic structures, which we use to handle sums of squares, do not apply in the
same generality to SONCs. We find this not at all surprising from the point of view that
in the 19th century Hilbert initially used SOS as a certificate for nonnegativity and many
of the algebraic structures in question where developed afterwards with Hilbert’s results
in mind; see [Rez00] for a historic overview. Our previous work shows that SONCs,
in contrast, can, e.g., very well be analyzed with combinatorial methods. We thus see
Theorem 5.1 as further evidence about the very different behavior of SONCs and SOS

OPTIMIZATION OVER THE BOOLEAN HYPERCUBE VIA SONCS

17

and as an encouragement to take methods beside the traditional real algebraic ones into
account for the successful application of SONCs in the future.
References
[ABS10]

S. Arora, B. Barak, and D. Steurer, Subexponential algorithms for unique games and related
problems, FOCS, 2010, pp. 563–572.
[ARV09]
S. Arora, S. Rao, and U.V. Vazirani, Expander flows, geometric embeddings and graph partitioning, J. ACM 56 (2009), no. 2, 5:1–5:37.
[BCG09]
M. H. Bateni, M. Charikar, and V. Guruswami, Maxmin allocation via degree lower-bounded
arborescences, STOC, 2009, pp. 543–552.
[BHK` 16] B. Barak, S.B. Hopkins, J.A. Kelner, P. Kothari, A. Moitra, and A. Potechin, A nearly tight
sum-of-squares lower bound for the planted clique problem, IEEE 57th Annual Symposium
on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New
Brunswick, New Jersey, USA, 2016, pp. 428–437.
[BRS11]
B. Barak, P. Raghavendra, and D. Steurer, Rounding semidefinite programming hierarchies
via global correlation, FOCS, 2011, pp. 472–481.
[BS14]
B. Barak and D. Steurer, Sum-of-squares proofs and the quest toward optimal algorithms,
Electronic Colloquium on Computational Complexity (ECCC) 21 (2014), 59.
[BS16]
, Proofs, beliefs, and algorithms through the lens of sum-of-squares, 2016.
[CGM13] M. Cygan, F. Grandoni, and M. Mastrolilli, How to sell hyperedges: The hypermatching
assignment problem, SODA, 2013, pp. 342–351.
[Che07]
K.K.H. Cheung, Computation of the Lasserre ranks of some polytopes, Math. Oper. Res. 32
(2007), no. 1, 88–94.
[Chl07]
E. Chlamtac, Approximation algorithms using hierarchies of semidefinite programming relaxations, FOCS, 2007, pp. 691–701.
[CLO15]
D.A. Cox, J. Little, and D. O’Shea, Ideals, varieties, and algorithms, fourth ed., Undergraduate Texts in Mathematics, Springer, Cham, 2015, An introduction to computational algebraic
geometry and commutative algebra.
[CS08]
E. Chlamtac and G. Singh, Improved approximation guarantees through higher levels of SDP
hierarchies, APPROX-RANDOM, 2008, pp. 49–62.
[CT]
E. Chlamtac and M. Tulsiani, Convex relaxations and integrality gaps, to appear in Handbook
on semidefinite, conic and polynomial optimization, Springer.
[DIdW17] M. Dressler, S. Iliman, and T. de Wolff, A Positivstellensatz for Sums of Nonnegative Circuit
Polynomials, SIAM J. Appl. Algebra Geom. 1 (2017), no. 1, 536–555.
[dlVKM07] W.F. de la Vega and C. Kenyon-Mathieu, Linear programming relaxations of maxcut, SODA,
2007, pp. 53–61.
[dW15]
T. de Wolff, Amoebas, nonnegative polynomials and sums of squares supported on circuits,
Oberwolfach Rep. (2015), no. 23, 53–56.
[GHP02]
D. Grigoriev, E.A. Hirsch, and D.V. Pasechnik, Complexity of semi-algebraic proofs, STACS,
2002, pp. 419–430.
[GLS88]
M. Grötschel, L. Lovász, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, vol. 2, Springer, 1988.
[Gri01]
D. Grigoriev, Complexity of positivstellensatz proofs for the knapsack, Comput. Complexity
10 (2001), no. 2, 139–154.
[GS11]
V. Guruswami and A. K. Sinop, Lasserre hierarchy, higher eigenvalues, and approximation
schemes for graph partitioning and quadratic integer programming with psd objectives, FOCS,
2011, pp. 482–491.
[GV01]
D. Grigoriev and N. Vorobjov, Complexity of null-and positivstellensatz proofs, Ann. Pure
App. Logic 113 (2001), no. 1-3, 153–160.

18

[GW95]

MAREIKE DRESSLER, ADAM KURPISZ, AND TIMO DE WOLFF

M.X. Goemans and D.P. Williamson, Improved approximation algorithms for maximum cut
and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach. 42
(1995), no. 6, 1115–1145.
[IdW16]
S. Iliman and T. de Wolff, Amoebas, nonnegative polynomials and sums of squares supported
on circuits, Res. Math. Sci. 3 (2016), 3:9.
[Kha80]
L.G. Khachiyan, Polynomial algorithms in linear programming, USSR Computational Mathematics and Mathematical Physics 20 (1980), no. 1, 53 – 72.
[KLM16] A. Kurpisz, S. Leppänen, and M. Mastrolilli, Sum-of-squares hierarchy lower bounds for
symmetric formulations, Integer Programming and Combinatorial Optimization - 18th International Conference, IPCO 2016, Liège, Belgium, June 1-3, 2016, Proceedings, 2016, pp. 362–
374.
[KLM17a]
, On the hardest problem formulations for the 0/1 lasserre hierarchy, Math. Oper.
Res. 42 (2017), no. 1, 135–143.
, An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable
[KLM17b]
problem, Math. Program. 166 (2017), no. 1-2, 1–17.
[KR00]
M. Kreuzer and L. Robbiano, Computational commutative algebra. 1, Springer-Verlag, Berlin,
2000.
[Las01]
J.B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J.
Optim. 11 (2000/01), no. 3, 796–817.
[Lau03a]
M. Laurent, A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations
for 0-1 programming, Math. Oper. Res. 28 (2003), no. 3, 470–496.
[Lau03b]
, Lower bound for the number of iterations in semidefinite hierarchies for the cut
polytope, Math. Oper. Res. 28 (2003), no. 4, 871–883.
, Sums of squares, moment matrices and optimization over polynomials, Emerging
[Lau09a]
applications of algebraic geometry, IMA Vol. Math. Appl., vol. 149, Springer, New York,
2009, pp. 157–270.
, Sums of squares, moment matrices and optimization over polynomials, Emerging
[Lau09b]
applications of algebraic geometry, IMA Vol. Math. Appl., vol. 149, Springer, New York,
2009, pp. 157–270.
[Lov79]
L. Lovász, On the shannon capacity of a graph, IEEE Trans. Inform. Theory 25 (1979), 1–7.
[LRS15]
J.R. Lee, P. Raghavendra, and D. Steurer, Lower bounds on the size of semidefinite programming relaxations, STOC, 2015, pp. 567–576.
[Mas17]
M. Mastrolilli, High degree sum of squares proofs, bienstock-zuckerberg hierarchy and CG
cuts, Integer Programming and Combinatorial Optimization - 19th International Conference,
IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings, 2017, pp. 405–416.
[MM09]
A. Magen and M. Moharrami, Robust algorithms for on minor-free graphs based on the
Sherali-Adams hierarchy, APPROX-RANDOM, 2009, pp. 258–271.
[MPW15] R. Meka, A. Potechin, and A. Wigderson, Sum-of-squares lower bounds for planted clique,
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing,
STOC 2015, Portland, OR, USA, June 14-17, 2015, 2015, pp. 87–96.
[Nes00]
Y. Nesterov, Global quadratic optimization via conic relaxation, pp. 363–384, Kluwer Academic Publishers, 2000.
[O’D17]
R. O’Donnell, SOS is not obviously automatizable, even approximately, 8th Innovations in
Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA,
USA, 2017, pp. 59:1–59:10.
[Par00]
P. Parrilo, Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization, PhD thesis, California Institute of Technology, 2000.
[Put93]
M. Putinar, Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J. 42
(1993), no. 3, 969–984.
[Rez89]
B. Reznick, Forms derived from the arithmetic-geometric inequality, Math. Ann. 283 (1989),
no. 3, 431–464.

OPTIMIZATION OVER THE BOOLEAN HYPERCUBE VIA SONCS

[Rez00]

[RT12]
[RW17]

[Sho87]
[Zie07]

19

, Some concrete aspects of Hilbert’s 17th Problem, Real algebraic geometry and ordered structures (Baton Rouge, LA, 1996), Contemp. Math., vol. 253, Amer. Math. Soc.,
Providence, RI, 2000, pp. 251–272.
P. Raghavendra and N. Tan, Approximating csps with global cardinality constraints using sdp
hierarchies, SODA, 2012, pp. 373–387.
P. Raghavendra and B. Weitz, On the bit complexity of sum-of-squares proofs, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14,
2017, Warsaw, Poland, 2017, pp. 80:1–80:13.
N. Shor, Class of global minimum bounds of polynomial functions, Cybernetics 23 (1987),
no. 6, 731–734.
G.M. Ziegler, Lectures on polytopes, Springer Verlag, 2007.

Mareike Dressler, Goethe-Universität, FB 12 – Institut für Mathematik, Postfach 11
19 32, 60054 Frankfurt am Main, Germany
E-mail address: dressler@math.uni-frankfurt.de
Adam Kurpisz, ETH Zürich – Department of Mathematics, Rämistrasse 101, 8092 Zürich,
Switzerland
E-mail address: adam.kurpisz@ifor.math.ethz.ch
Timo de Wolff, Technische Universität Berlin, Institut für Mathematik, Straße des
17. Juni 136, 10623 Berlin, Germany
E-mail address: dewolff@math.tu-berlin.de

