Approximating Rectangles by Juntas and
Weakly-Exponential Lower Bounds for LP Relaxations of
CSPs

arXiv:1610.02704v4 [cs.CC] 30 Dec 2017

Pravesh K. Kothari *
IAS and Princeton University, NJ, USA
Raghu Meka †
University of California, Los Angeles, CA, USA
Prasad Raghavendra ‡
University of California, Berkeley, CA, USA

Abstract
We show that for constraint satisfaction problems (CSPs), weakly-exponential size linear programming relaxations are as powerful as nΩ(1) -rounds of the Sherali-Adams linear programming
hierarchy. As a corollary, we obtain sub-exponential size lower bounds for linear programming
relaxations that beat random guessing for many CSPs such as MAX-CUT and MAX-3SAT. This
is a nearly-exponential improvement over previous results; previously, it was only known that
linear programs of size no(log n) cannot beat random guessing for any CSP [CLRS13].
Our bounds are obtained by exploiting and extending the recent progress in communication
complexity for "lifting" query lower bounds to communication problems. The main ingredient
in our results is a new structural result on “high-entropy rectangles” that may of independent
interest in communication complexity.

Part of the work was done while the author visited UC Berkeley.
raghum@cs.ucla.edu. Supported by NSF CCF-1553605. Part of this talk was done while the author was visiting the
Simons Institute for Theory of Computing, Berkeley as part of the program on Fine-grained Complexity.
‡
prasad@cs.berkeley.edu. Supported by NSF CCF-1408643, CCF-1343104 and the Sloan Fellowship
* kothari@cs.princeton.edu.

†

1

Introduction

Translating a combinatorial problem over a discrete domain to a problem in continuous space
has been an important concept in computer science over the last few decades; in this vein, linear
programming relaxation is one of the most used techniques for algorithm design. In this work we
prove limitations on the power of linear programs (LPs) as applied to constraint satisfaction problems
(CSPs).
Constraint satisfaction problems such as MAX-3SAT or MAX-3XOR or MAX-CUT are some of
the most well-studied problems in approximation algorithms as well as combinatorial optimization.
Here we show unconditional lower bounds for approximately solving CSPs by LPs. Informally, we
Ω(1)
show that for many CSPs such as MAX-3SAT, MAX-3XOR, or MAX-CUT, no LP of size 2n can
beat the trivial approximation factor (7/8 for MAX-3SAT, 1/2 for MAX-3XOR, 1/2 for MAX-CUT);
we also show similar results for vertex-cover. Previously, such lower bounds only applied to LPs of
size at most nΩ((log n)/(log log n)) [CLRS13].
The core of our result above is a new structural result about rectangles that has various applications in communication complexity in the context of lifting query lower bounds to communication
lower bounds.

1.1

CSPs, Linear programming relaxations, Sherali-Adams hierarchy

A MAX-CSP (henceforth referred to only as CSP) is defined by a predicate P : {−1, 1}k → {0, 1}.
An instance of the CSP, I, is defined by a collection of k-tuples of literals C1 , C2 , . . . , Cm on n
Boolean variables (x1 , x2 , . . . , xn ) 1 . The algorithmic problem is to find an assignment to the variables
x = (x1 , . . . , xn ) so as to maximize the number of satisfied constraints:
opt(I) = max

m
X

x∈{−1,1}n

P(Ci (x)) ≡ max I(x),
x∈{−1,1}n

i=1

(1.1)

P
where we define I(x) = m
i=1 P(Ci (x)).
For example, MAX-CUT corresponds to the case where the predicate P : {−1, 1}2 → {0, 1} is
defined by P(a, b) = (1 − ab)/2 with instances corresponding to graphs.
Here we consider a broad-class of linear programming relaxations for CSPs obtained by
linearizing the objective function I(x). Formally, given a predicate P, and an integer D, we want:
Definition 1.1 (Linearization of a CSP).

1. A vector vx ∈ RD for every x ∈ {−1, 1}n .

2. A vector wI ∈ RD for every instance I of the CSP.
3. For every assignment x and every instance I, I(x) = hwI , vx i.
Given a linearization as above, we can define a relaxation of the CSP as follows. For a polytope
P ⊆ RD with {vx : x ∈ {−1, 1}n } ⊆ P, we look at the linear program
optP (I) = maxhwI , yi.
y∈P

1

Throughout this article, we will use {−1, 1} to denote Boolean inputs

1

Clearly, opt(I) 6 optP (I). The complexity or size of the relaxation is defined as the number of facets
(or inequalities) needed to describe the polytope P.
Approximating CSPs by LP relaxations. Consider a CSP defined by a predicate P : {−1, 1}k →
{0, 1}. A LP relaxation for the CSP is a sequence of polytopes P ≡ {Pn : n > 1} where for each n > 1,
Pn is a relaxation for n-variable instances of the CSP as defined above. For a function s : N → N, we
say P has size at most s(n) if each Pn has size at most s(n).
For 0 < c 6 s 6 1, we say P achieves a (c, s)-approximation for the CSP if for n-variable instances
I with opt(I) 6 s, optPn (I) 6 c. Similarly, for 0 6 α 6 1, we say P achieves a α-approximation if
for all n > 1, opt(I) > α · optPn (I). In the latter case, we also say P has integrality-gap at most (1/α).
The above framework introduced in the work of [CLRS13] generalizes the extended formulation
framework of Yannakakis [Yan88] and its adaptation to approximation algorithms as formulated in
[BFPS15]. Furthermore, LPs arising out of the Lovasz-Schriver (LS) [LS91] or the Sherali-Adams
[SA90] hierarchies are captured within this framework.
We prove that despite their apparent generality, when it comes to CSPs, general linear programs
as above, and hence all extended formulations, are only as powerful as those obtained from the
Sherali-Adams hierarchy:
Theorem 1.2. There exist constants 0 < h < H such that the following holds. Consider a function f : N → N.
Suppose that the f (n)-round Sherali-Adams relaxation for a CSP cannot achieve a (c, s)-approximation on
instances on n variables. Then, no LP relaxation of size at most nh f (n) can achieve a (c, s)-approximation for
the CSP on nH variables.
Charikar, Makarychev, and Makarychev [CMM09] showed that for all ε > 0, there is a constant
γ(ε) such that nγ(ε) -round Sherali-Adams relaxation for MAX-CUT has integrality gap at least 2 − ε.
Similarly, it follows from the works of Grigoriev [Gri01] (and from that of Schoenebeck [Sch08]) that
Ωε (n)-round Sherali-Adams relaxations have integrality gap at least 2 − ε, 8/7 − ε for MAX-3XOR
and MAX-3SAT respectively. As a corollary, we get the following lower bounds for solving CSPs by
linear programming relaxations.
Corollary 1.3. For some universal constant H > 1, for every ε > 0, there exist constants c1 (ε), c2 (ε), c3 (ε)
1/H
such that the following hold: no LP relaxation of size less than 2c1 (ε)n has integrality gap less than
1/H
(8/7 − ε) for MAX-3SAT; no LP relaxation of size less than 2c2 (ε)n has integrality gap less than (2 − ε) for
c
(ε)
MAX-3XOR; no LP relaxation of size less than 2n 3 has integrality gap less than (2 − ε) for Max-CUT.
We also get similar bounds more generally for CSPs defined by pairwise-independent predicates
by combining Theorem 1.2 with known integrality-gaps for such CSPs ([BGMT12]).
The above results for CSPs are established through a more general claim on non-negative rank of
a class of matrices referred to as pattern matrices. We explain this connection and results next.

1.2

Lifting degree lower bounds to rank lower bounds

In the seminal work introducing extended formulations, Yannakakis showed that the extended
formulation complexity of an optimization problem is precisely the non-negative rank of the associated
slack matrix. In [BFPS15], this connection was subsequently extended to approximation by linear
2

programs. All known lower bounds on the size of extended formulations rely on this connection as
do we.
Definition 1.4 (Non-negative Rank). Let M be a non-negative matrix. The non-negative rank of
M, denoted by rank+ (M) is the least positive integer r such that there exist non-negative rank 1
P
matrices M1 , . . . , Mr such that M = ri=1 Mi .
Proving lower bounds on non-negative rank of specific matrices is often non-trivial; a significant
breakthrough towards proving such lower bounds was achieved by the work of [FMP+ 15] who
showed a connection between communication complexity lower bounds and non-negative rank.
We give a tight characterization of the non-negative rank of a broad-class of matrices–pattern
matrices–that were studied before in communication complexity [RM99, Raz03, She11].
Definition 1.5 (Pattern Matrix). Fix positive integers n and q. Given functions f : {−1, 1}n → R and
1 : [q] × [q] → {−1, 1}, the composed function f ◦ 1⊗n : [q]n × [q]n → R is defined as,

def
f ◦ 1⊗n (x, y) = f 1(x1 , y1 ), . . . , 1(xn , yn ) ,
1

where we have xi , yi ∈ [q] for all i ∈ [n]. The pattern matrix M f is the truth-table of the composed
function f ◦ 1⊗n expressed as a matrix, i.e., it is a matrix with rows and columns indexed by [q]n
with,
def
1
M f (x, y) = f ◦ 1⊗n (x, y) .
The function 1 : [q] × [q] → {−1, 1} is referred to as the gadget function. Throughout this work,
we will use a slightly modified (in order to ensure balancedness) version of the Boolean inner-product
function as the gadget 1. Specifically we will set q = 2b for b ∈ N, identify [q] with {0, 1}b and define
def

b

1 : {0, 1}b × {0, 1}b → {−1, 1} given by 1(x, y) = (−1)x1 ⊕y1 · (−1)⊕i=1 xi yi .
1

With this choice of the gadget function 1, we will use Mbf to denote the pattern matrix M f ; we also
drop the superscript b and use M f to denote Mbf when b is clear from context.
Our main result characterizes the non-negative rank of pattern matrices M f by a corresponding
measure of f that we define next.
Definition 1.6 (Juntas and Non-negative Degree). A function h : {−1, 1}n → R is a d-junta if it only
depends on at most d coordinates. A function h : {−1, 1}n → R>0 is a conical d-junta if it can be
written as a non-negative linear combination of non-negative d juntas.
For any f : {−1, 1}n → R>0 , the non-negative degree of f , written as deg+ ( f ), is the least positive
integer d such that f can be written as a conical d-junta.
We show that for any non-negative function f , the non-negative rank of M f is essentially
characterized by the non-negative degree of f . Indeed, it is easy to check that
!
n
b
rank+ (M f ) 6
· 2b·deg+ ( f ) .
(1.2)
deg+ ( f )
3

We show a nearly matching lower bound for rank+ (Mbf ); specifically, we show that if small
positive shifts of f have2 high non-negative degree, then rank+ (M f ) is correspondingly large.
Theorem 1.7 (rank+ (M f ) vs deg+ ( f )). There exist constants c, C > 0 such that the following holds. Let
f : {−1, 1}n → R>0 be such that E[ f ] = 1. Then,
rank+ (Mbf ) > 2c·b·(deg+ ( f +η)−8deg( f )) .
for all η > 1/n and b > C(log n).
Note that by Equation 1.2, for b > log n, rank+ (Mbf ) 6 22b·deg+ ( f ) . Thus in the interesting regime
when deg+ ( f )  deg( f ), the above theorem is tight up to constant factors (in the exponent) and
working with deg+ ( f + η).

1.3

Previous work: Approximate non-negative rank versus non-negative rank

The above result should be compared with similar results in [GLM+ 15, LRS15] . Although they also
obtain similar lifting theorems, a crucial difference is that they lower bound the approximate nonnegative rank of lifted matrices. For a non-negative matrix M, and ε > 0, define the ε-approximate
non-negative rank as
rankε+ (M) = min{rank+ (M0 ) : kM0 − Mk∞ 6 εkMk∞ }.
Clearly, rankε+ (M) 6 rank+ (M) for all ε > 0. At a high-level, the previous works show lower
bounds on rankε+ (M f ) (in terms of the approximate non-negative junta degree of f ). Similarly, while
[GLM+ 15] show a separation between rankε+ , rankδ+ for some constants 0 < ε < δ < 1, the resulting
matrices have large rank. Such lifting theorems are not enough to obtain our applications to CSPs –
Theorem 1.2, Corollary 1.3 – as matrices arising in these applications in fact have small approximate
non-negative rank (roughly nO(log(1/ε)) ) and small rank. This was one of the main reasons why the
previous works only obtained quasi-polynomial size lower bounds.
In fact, before our work, the best separation between rankε+ , rank and rank+ was only quasipolynomial. As a corollary of our results, we obtain weakly-exponential separation for an explicit
matrix:
Theorem 1.8. For all ε > 0, there exist constants 0 < cε , Cε such that the following holds. There exists an
N×N such that rank(M), rankε (M) 6 (log N)Cε , and rank (M) > N cε .
explicit non-negative matrix M ∈ R>0
+
+

1.4

Applications in Communication Complexity

Analyzing lifted functions or pattern matrices has been a very useful tool in communication
complexity over the last few years and our work builds on the techniques of [GLM+ 15] who show
lifting theorems for various rectangle-based communication measures. Our main decomposition
theorem, Theorem 2.10, can be used to recover the main results of [GLM+ 15]. Indeed, the main
results of [GLM+ 15] follow from a structural result about approximating rectangles by juntas –
2

Note that deg+ ( f + η) 6 deg+ ( f ) for all η > 0.

4

an analogue of Theorem 2.7 that in turn follows easily from our decomposition theorem. For a
more detailed comparison, see the discussion at the beginning of Section 6.3. We believe that our
decomposition theorem could lead to other such applications in future.

2
2.1

Proof overview
Lifting deg+ lower bounds to non-negative rank

The proof of Theorem 1.7 consists of two steps. First, we show that if rank+ (M f ) is small for
a function f , then f can be approximated by a conical junta under a carefully chosen notion of
approximation. Second, we show that if f can be so approximated by a conical junta, then deg+ ( f + η)
is small for η  1.
Towards making this outline more precise, we begin by defining a notion of approximate conical
juntas that plays an important role in our proofs. We first state some basic notations that we use
throughout:
• For any function f , E[ f ] denotes the expectation of f on the uniform distribution over its
domain.
• For any x ∈ {−1, 1}n and I ⊆ [n], we write xI to denote the projection of x on to the coordinates
in I.
• A Boolean conjunction C : {−1, 1}n → R>0 is defined by a subset I ⊆ [n] of variables and α an
assignment to the variables in I by C(x) = 2|I| · 1[xI = α]. We say C is a d-conjunction if |I| 6 d.
Observe that we choose a non-standard scaling that satisfies E[C] = 1.
• For any S ⊆ [n], the parity function χS (x) = Πi∈S xi for any x ∈ {−1, 1}n . Any function
P
f : {−1, 1}n → R has the Fourier expansion f (x) = S⊆[n] fb(S)χS (x). The terms fb(S) are the
Fourier coefficients of f .
Definition 2.1 (ε-decaying functions). For 0 < ε < 1, a function h : {−1, 1}n → R is said to be
ε-decaying if E[h] = 0 and for every I ⊆ [n], |b
h(I)| 6 ε|I| .
Definition 2.2 ((ε, δ)-approximate conical d-junta). For ε, δ ∈ (0, 1), a function f : {−1, 1}n → R>0
with E[ f ] = 1 is said to be an (ε, δ)-approximate conical d-junta if f can be written as
X
f (z) =
λi Ci (z) · (1 + hi (z)) + γ(z)
(2.1)
i∈[N]

for d-conjunctions C1 , . . . , CN , ε-decaying functions h1 , . . . , hN , λ1 , . . . , λN ∈ R>0 with
a function γ : {−1, 1}n → R>0 such that E[γ] 6 δ.

i λi

P

6 1, and

Notice that the approximation by conical-juntas has two distinct error terms, the multiplicative
errors due to the ε-decaying functions {hi } and the additive error in the form of γ.
The first step in proving Theorem 1.7 is the following lemma saying that if rank+ (M f ) is small,
then f is an approximate conical d-junta for small d.
5

Lemma 2.3 (Non-negative rank to Approximate Conical Juntas). There exists a constant α1 > 1
such that the following holds. For b > α1 log n, every function f : {−1, 1}n → R>0 with E[ f ] = 1 is a
(2−b/2 , 2−bd/α1 )-approximate conical d-junta for all d > α1 (log rank+ (Mbf ))/b.
We defer the sketch of the proof of the lemma to the next section and continue with our outline
of the proof of Theorem 1.7.
Given the above lemma, the final step in proving Theorem 1.7 is to show a connection between
deg+ ( f ) and (ε, δ)-approximation by conical juntas. Specifically, we show a certain robustness of the
class of conical juntas: if a function f is an (ε, δ)-approximate conical d-junta for sufficiently small ε
and δ, then the function f + η is an exact conical 8d-junta for a small constant η.
Lemma 2.4. Suppose f : {−1, 1}n → R>0 with E[ f ] 6 1 is an (ε, δ)-approximate conical d-junta for
ε < 1/n4 and some d > deg( f ) and δ < 1/n8d then

deg+


1
f+
6 8d
n

Lemma 2.3 and Lemma 2.4 together imply Theorem 1.7 almost immediately by setting the
parameters appropriately; see Section 4.
We defer the proof of Lemma 2.4 to Section 4.2. In what follows, we sketch the key ideas
underlying the proof of Lemma 2.3.

2.2

Approximating Rectangles by Conical Juntas

We now sketch the proof of Lemma 2.3. To do so, we need the following basic definition3 .
Definition 2.5 (Density). A function p : [q]n → R>0 is said to be a density if E[p(x)] = 1. A density p
defines a corresponding random variable X on [q]n where Pr[X = x] = p(x) · q−n . We denote X ∼ p
this random variable.
Recall the statement of the lemma: we have a density f on {−1, 1}n such that M f has small
non-negative rank and we want to show that f is a low-degree approximate conical junta. Let
P
rank+ (M f ) = r. By definition, M f = i∈[r] Mi where each Mi is a non-negative rank one matrix;
further, by appropriate normalization, we can assume that Mi = λi ui v†i , where ui , vi are densities
on [q]n and λi > 0. This decomposition of the matrix M f into non-negative rank 1 matrices {Mi },
yields a corresponding decomposition of the function f into a sum of non-negative functions, one
corresponding to each rank one matrix Mi .
Formally, let us denote by G : [q]n × [q]n → {−1, 1} the function G := 1⊗n . By definition, the

entries of the matrix M f are given by M f (x, y) = f G(x, y) . For z ∈ {−1, 1}n , let (X, Y) ∼ G−1 (z)
denote a uniformly random pair chosen from the set of pairs G−1 (z) ⊆ [q]n × [q]n . With this notation,
X
X
[Mi (X, Y)] =
[ui (X)vi (Y)] .
f (z) =
E
M f (X, Y) =
E
λi
E
(2.2)
(X,Y)∼G−1 (z)

i∈[r]

(X,Y)∼G−1 (z)

i∈[r]

(X,Y)∼G−1 (z)

3
We work with densities (instead of equivalently working with probability density functions or just non-negative
functions) as keeping track of errors is cleaner under this normalization.

6

Borrowing terminology from communication complexity, we will refer to the rank one matrices
as rectangles. In order to approximate the function f by a conical junta, it suffices to approximate
the terms corresponding to each rectangle by a conical junta. We exhibit such an approximation for
all large rectangles.
Towards this end, for two densities u, v on [q]n , define Accu,v : {−1, 1}n → R>0 by
ui v†i

Accu,v (z) =

E

[u(X)v(Y)].

(X,Y)∼G−1 (z)

(2.3)

Note that E[Acc] = E[u(x)v(y)] = 1. Thus, Acc is a density on {−1, 1}n . Indeed, it is easy to check
that Accu,v is the density of the random variable G(X, Y) for X ∼ u and Y ∼ v (X, Y independent).
Using this definition in (2.2), we get
f (z) =

r
X

λi · Accui ,vi (z).

i=1

This motivates the study of functions Accu,v for rectangles. Indeed, structural results characterizing such functions form the core of previous results on pattern matrices [GLM+ 15, She11]. We
show that functions Accu,v as above are simple when the rectangle u × v is large. To formalize this we
need the notion of min-entropy.
Definition 2.6 (Min-Entropy). For a density u on [q]n , the min-entropy of u, H∞ (u), is defined by45
H∞ (u) = min n log (qn /u(x)).
x∈{−1,1}

For intuition, it is helpful to think of the special case where the densities ui , vi correspond to
uniform distributions over some subsets Ui , Vi of [q]n respectively. The rectangle Mi is said to
be large, if the sets Ui and Vi are both large, of size at least qn /2C for C  n. More generally, the
rectangle Mi is large if the distributions ui , vi each have min-entropy at least n log q − C. We will
refer to C as the min-entropy deficiency.
Since M is the sum of r rectangles, one can argue that it is approximated by large rectangles
whose min-entropy deficiency is at most O(log r). The contribution from all the small rectangles can
be included into the additive error term γ(z) in the approximation for f . The main work lies in
showing that every large rectangle is approximated by conical juntas.
Theorem 2.7 (Junta Approximation). There exists a constant α2 > 1 such that the following holds. Let
u, v be densities over [q]n with q = 2b such that H∞ (u) + H∞ (v) > 2b(n − t). Then, for all b > α2 log n and
d > α2 t, Accu,v {−1, 1}n → R>0 is a (2−0.5b , (2−0.5b )d )-approximate conical d-junta.
[GLM+ 15] also show a similar, but weaker, junta approximation theorem. In the present context,
they essentially show that Accu,v can be approximated as Accu,v (z) = (1 ± 2−Ω(b) ) · h(z) ± 2−Ω(bd) where
h is a conical d-junta. Note that the multiplicative error is only of the order 2−Ω(b) and this was
a critical bottleneck in using their results to prove a lifting theorem for non-negative rank as in
Theorem 1.7 (instead of for approximate non-negative rank). In comparison, we get exponentially
small error in terms of approximate conical d-juntas. The latter is in fact stronger; a straightforward
extension of our arguments can in fact recover the corresponding statement of [GLM+ 15].
4
5

Note that this is the same as the more standard definition of minx∈{−1,1}n log(1/ Pr[X = x]) where X ∼ u.
Throughout this work, all logarithms are to the base 2.

7

2.3

Decomposing High-Entropy Distributions

The proof of Theorem 2.7 relies on a crucial decomposition lemma for high-entropy distributions
that may be of independent interest. Let u, v be two densities over [q]n with min-entropy at least
(n − C) · log q for some C  n and let X ∼ u, Y ∼ v be sampled independently.
A particularly simple class of high min-entropy distributions are those where a subset of C
coordinates of X are fixed, while the rest are uniformly random. That is, for some set I ⊆ [n] with
|I| 6 C, XI is a fixed string whereas X[n]\I is uniformly random over [q][n]\I . Similarly, Y could
satisfy a similar property for a set J ⊆ [n] with |J| 6 C. An especially desirable scenario is one
where X, Y are aligned in the sense that I = J. For such aligned distributions, the random variable
Z = 1n (X, Y) ∈ {−1, 1}n is such that ZI is fixed while ZI is uniformly random. In other words, the
probability density of Z is a C-junta depending only on I.
We will show that as long as X, Y have high min-entropy, the product distribution X × Y can be
decomposed into distributions that are essentially as simple and aligned as in the above discussion.
To this end, we next introduce the notion of blockwise-dense distributions; they were first defined
in [GLM+ 15] and play a crucial role here.
Definition 2.8. A distribution X on [q]n is blockwise-dense if for every I ⊆ [n], H∞ (XI ) > 0.8·log q·|I|.
We say a density u on [q]n is blockwise-dense if X ∼ u is blockwise-dense .
Definition 2.9. A distribution X on [q]n is a d-CBD (“conjunctive blockwise-dense”) distribution if
for some set of coordinates I ⊆ [n], |I| 6 d, H∞ (XI ) = 0 and for every J ⊆ [n] \ I, H∞ (X J ) > 0.8 · log q · |J|.
We refer to d as the degree of the CBD distribution, and the set of blocks I as the fixed blocks. We say
two d-CBD distributions X, Y on [q]n are aligned if the fixed blocks I are the same in both.
Analogously, we say two densities u, v over [q]n are aligned d-CBD if the random variables X, Y
are aligned d-CBD distributions for X ∼ u, Y ∼ v.
The technical core of our results is the following lemma stating that any two independent
high-entropy densities u, v over [q]n can be approximated by a convex combination of aligned
d-CBD densities for small d. The error of the approximation will depend on the entropy deficiency
of u ⊗ v and the degree of the CBD distributions used in the approximation.
Theorem 2.10. There exists a constant c > 1 such that the following holds. For n > 1 and q > nc , let u, v
be two densities on [q]n with H∞ (u) + H∞ (v) > 2(n − t) · log q. Then, for all d > ct/(log q), the product
density u ⊗ v on [q]n × [q]n can be written as a convex combination of densities u1 ⊗ v1 , u2 ⊗ v2 , . . . , uN ⊗ vN ,
P
and γerr , i.e., u ⊗ v = N
i=1 λi ui ⊗ vi + λerr γerr , such that
P
• 0 6 λ1 , . . . , λN , λerr 6 1, N
i=1 λi + λerr = 1.
• |λerr | < q−Ω(d) .
• For every i ∈ [N], Xi ∼ ui , Yi ∼ vi are aligned d-CBD distributions.
Theorem 2.7 follows easily from the above using some “extractor”-like properties (cf. Fact 5.2)
of the slightly modified inner-product function 1. We defer the details of the proof of the theorem
to the corresponding section.
8

2.4

Organization

We present the proof in a top-down manner: We first prove Theorem 1.7 assuming Theorem 2.7.
We then prove Theorem 2.7 assuming Theorem 2.10 (this is almost immediate). Finally, we prove
Theorem 2.10. We then prove Theorem 1.2, Corollary 1.3 in Section 7.

3

Preliminaries

We describe some basic notation that we use throughout6 .

3.1

Basic Notation

1. Pnd denotes the collection of all polynomials of degree at most d on n variables on {−1, 1}n .
2. 1(E) is the indicator for the event E normalized to have mean 1. That is, 1(E) is 0 when E
doesn’t happen and 1/ P[E] when E happens.
3. For any function f , E[ f ] denotes the expectation of f on the uniform distribution over its
domain.
4. For matrices M, E[M] denotes the expectation of M(x, y) under x, y being uniformly random
indices for its rows and columns.
5. For any x ∈ {−1, 1}n and I ⊆ [n], we write xI to denote the projection of x on to the coordinates
in I.
6. A Boolean conjunction C : {−1, 1}n → R>0 is defined by a subset I ⊆ [n] of variables and α an
assignment to the variables in I by C(x) = 1[xI = α]. We say C is a d-conjunction if |I| 6 d.
Observe that we choose a non-standard scaling that satisfies E[C] = 1.
7. For any S ⊆ [n], the parity function χS (x) = Πi∈S xi for any x ∈ {−1, 1}n . Any function
P
f : {−1, 1}n → R has a Fourier expansion: f (x) = S⊆[n] fb(S)χS (x). The terms fb(S) are the
Fourier coefficients of f .

3.2

Sherali-Adams Linear Programming Relaxations

Our results relate arbitrary linear programming relaxations for CSPs to the Sherali-Adams hierarchy.
We discuss the latter class of linear programs next. We begin with the definition of a degree d
pseudo-expectation
Definition 3.1 (Sherali-Adams Pseudoexpectation). A degree d Sherali-Adams pseudoexpectation,
Ẽ, is a linear operator on the space of degree at most d polynomials, Pnd , such that
1. For every non-negative p ∈ Pnd that depends on only d variables, Ẽ[p] > 0, and
6

To have all notations together, some are repeated from the introduction.

9

2. Ẽ[1] = 1.
Since Ẽ is a linear, it is completely specified by its values on multilinear polynomials, in particular
by the values Ẽ[χS (x)] for S ⊆ [n], |S| 6 d.
Sherali-Adams linear programming relaxations can be equivalently described using a collection
of probability distributions over local assignments. The above view is more convenient for us. We
refer the reader to [CLRS13] for a detailed discussion.
The degree d-Sherali-Adams linear programming relaxation for a CSP solves the following
optimization problem. Given an instance I of a k-ary CSP, we can canonically encode it as a
polynomial of degree k PI : {−1, 1}n → [0, 1] such that PI (x) = I(x) for all assignments x ∈ {−1, 1}n .
Then, the degree d-Sherali-Adams relaxation is
max Ẽ[PI (x)],

(3.1)

Ẽ

where Ẽ ranges over all degree d Sherali-Adams pseudoexpectations. We define SAd (I) as the
value of the the optimization problem (3.1). The above optimization problem can be solved using a
linear program on nO(d) variables and constraints. Note that opt(I) 6 SAd (I).
Sherali-Adams LP and Non-negative Degree:. Linear programming duality gives an elegant
characterization of the performance of Sherali-Adams LP on a CSP in terms of non-negative degree.
Fact 3.2 (Sherali-Adams value and Non-negative Degree [CLRS13]). Let P : {−1, 1}k → {0, 1} be a
predicate and I be an instance of CSP(P). Then, SAd (I) 6 c if and only if deg+ (c − I) 6 d.

4

Juntas, Rectangles, and Non-negative Rank of Lifted Matrices

In this section, we will show our main Theorem 1.7 assuming Theorem 2.7. Let f : {−1, 1}n → R>0
be as in the theorem with E[ f ] = 1, and let the gadget 1 : [q] × [q] → {−1, 1} and b be as in the
theorem. We will show that if rank+ (M f ) is small, then deg+ ( f + η) is small, where η = O(1/n).
Concretely, given a small rank non-negative factorization of M f , we use the factorization to get a
small-degree conical junta approximating f + η. As described in the introduction, this is done in
two modular steps: Lemmas 2.3, and 2.4. First, we show how Lemma 2.3 and Lemma 2.4 together
immediately imply Theorem 1.7.
Proof of Theorem 1.7. Fix a constant C such that C > max(16α1 , 1000) for α1 from Lemma 2.3. Let
R := rank+ (Mbf ). By Lemma 2.3, this implies that f is a (2−b/2 , 2−bd/α1 )-approximate conical d-junta
for d > α1 log R/b. For b > C log n, 2−b 6 min(1/n1000 , 1/n16α1 ). Hence, f is a (1/n500 , 1/n16d )approximate conical d-junta with d = max{dα1 log R/be, deg( f )}. By Lemma 2.4, this implies
that


α1 log R
1
deg+ f +
68·
+ 8deg( f ) ,
n
b
which yields the inequality,
1
R > 2Ω(b)·(deg+ ( f + /n)−8deg( f )) .

10

For the rest of this section we adopt the following assumptions:
Important Parameters.
• f : {−1, 1}n → R>0 with E[ f ] = 1.
• The block-length of the gadget b = C log n for a sufficiently large constant C.
• Recall that the gadget is defined at any x, y ∈ {0, 1}b by:
def

b

1(x, y) = (−1)x1 ⊕y1 · (−1)⊕i=1 xi yi .

4.1

Approximation by Approximate Conical Juntas

Here we prove Lemma 2.3 which we restate for convenience.
Lemma (Restatement of Lemma 2.3). There exists a constant α1 > 1 such that the following holds. For
b > α1 log n, every function f : {−1, 1}n → R>0 with E[ f ] = 1 is a (2−b/2 , 2−bd/α1 )-approximate conical
d-junta for all d > α1 (log rank+ (Mbf ))/b.
Proof. For the sake of brevity, let us set G := 1⊗n and R := rank+ (Mbf ). For every z ∈ {−1, 1}n , and
(x, y) ∈ G−1 (z), we have M f (x, y) = f (z). The high-level idea is as follows. From the definition of M f ,
we have
f (z) =
E
[M f (X, Y)].
(X,Y)∼G−1 (z)

Further, by definition of rank+ (M f ), the matrix M f can be expressed as a sum of rank+ (M f ) nonnegative rank-1 matrices. In turn, this yields a decomposition of f into a sum of a family of
non-negative functions. We then use Theorem 2.7 to approximate each of these functions by
approximate conical juntas, thereby yielding the desired approximation for f .
Concretely, from the definition of non-negative rank, there exists a collection of densities on
{−1, 1}bn , {ui | 1 6 i 6 R} and {vi | 1 6 i 6 R}, and a set of non-negative constants λ1 , λ2 , . . . , λR such
that
R
X
Mf =
λi ui v†i .
i=1

Observe that

R
X

λi =

i=1

Now, for any z ∈

R
X

λi E[ui v†i ] = E[M f ] = 1.

i=1

{−1, 1}n ,
f (z) =

E

[M f (X, Y)]

(X,Y)∈G−1 (z)

 R

X




=
E
λ
u
(X)v
(Y)

i
i
i

−1
(X,Y)∈G (z)
i=1

11

=
=

R
X
i=1
R
X

λi ·

E

[ui (X)vi (Y)]

(X,Y)∈G−1 (z)

λi · Accui ,vi (z).

i=1

(Recall the definition of Acc from Equation (2.3).)
In analogy with communication complexity, we will refer to the rank 1 matrices ui v†i as rectangles.
We will split the family of rectangles in to large and small. To this end, fix t = 4 log (R). A rectangle
ui v†i will be referred to as large, if the min-entropies of ui and vi are large. More precisely, let
Q = {i ∈ R | H∞ (ui ) + H∞ (vi ) > 2(n − t)(log q)}.
We can now write f as a sum f = J + δ1 where,
X
J(z) =
λi Accui ,vi (z)
i∈Q

and
δ1 (z) =

X

λi Accui ,vi (z).

i<Q

Now, for each i ∈ Q, by Theorem 2.7 applied to ui , vi , Accui ,vi is a (ε, εd )-approximate
conical
dP

0
0
d
d
junta for all d > α2 t. Therefore, J is an (ε, δ )-approximate conical d-junta with δ =
i∈Q λi · ε 6 ε .
Now we will bound the total additive error due to the small rectangles. Observe that for any
i < Q, λi 6 2−t/2 . This is because, λi E y [ui (x)vi (y)] = λi ui (x) 6 E y [M f (x, y)] = E[ f ] = 1 and similarly,
λi vi (y) 6 1 for any y. Further, recall that Accu,v is a density for all densities u, v. Thus,
X
X
E[
λi Aui ,vi ] 6
2−t/2 6 2−t/2 R.
i<Q

i<Q

Therefore, f = J + δ1 is an (ε, εd + 2−t/2 R)-approximate conical d-junta for all d > α2 t/b. Choosing
t = 4 log R and d = max{4α2 log R/b, 2 log R/b} proves the lemma.


4.2

Approximate Conical Juntas to Conical Juntas

Notation.
• C6D : cone of non-negative D-juntas on {−1, 1}n .
• L : {−1, 1}n → R: separating function.
In this section we will prove Lemma 2.4 which asserts that if f is a low-degree approximate
conical junta, then f + η is a low-degree conical junta for η sufficiently small.

12

Lemma (Restatement of Lemma 2.4). Suppose f : {−1, 1}n → R>0 with E[ f ] 6 1 is an (ε, δ)-approximate
conical d-junta for ε < 1/n4 and some d > deg( f ) and δ < 1/n8d then


1
deg+ f +
6 8d
n
At a high-level the proof is as follows. Suppose for the sake of contradiction that deg+ ( f + 1/n) >
8d. Then, there is a nice separating functional L such that hL, f i 6 −1/n, and hL, hi > 0 for
all h ∈ C68d . We then use further properties of the functional that the latter property implies
hL, hi > −1/n for all (ε, εd )-approximate conical d-junta - leading to a contradiction.
We first develop the requisite technical machinery concerning conical juntas and separating
functionals.
Lemma 4.1. Suppose deg( f ) 6 D < deg+ ( f + η). There exists a degree D function L : {−1, 1}n → R such
that:
1. E[L] = E[L · 1] = 1.
2. E[L f ] < −η.
3. E[Lh] > 0 for every conical D-junta h on {−1, 1}n .
b
4. |L(S)|
6 1 for every |S| 6 D.
5. kLk∞ 6 nD
Proof. Observe that the set of conical 6 D-juntas denoted by C6D is convex. On the other hand
from the hypothesis, we have that f + η < C6D . Thus, there exists a function L : {−1, 1}n → R such
that hL, hi > 0 for every h ∈ C6d but hL, ( f + η)i < 0. Moreover, since C6D and f + η are contained
in the linear subspace of degree D polynomials, without loss of generality, we can assume that L is
also a degree D polynomial.
The first three properties are simple to verify. Since the constant function 1 ∈ C6D , we can
assume (by rescaling, if needed) that hL, 1i = 1 giving us the first property. Further, since
hL, f i = L · ( f + η) − hL, ηi 6 −η giving us the second property. The third property follows from
our definition of L.
We next bound the Fourier coefficients of L. First observe that for any S ⊆ [n], |S| 6 D, 1 + χS
is a non-negative D-junta. Therefore, hL, 1 + χS i > 0 so that hL, χS i > −hL, 1i = −1. Similarly,
b
hL, 1 − χS i > 0 so that hL, χS i 6 1. Thus, |L(S)|
= |hL, χS i| 6 1.
P
P
D
b
b
The final property follows as kLk∞ = k S,|S|6D L(S)χ

S (x)k 6
|S|6D |L(S)| 6 n .
The following technical property of L constructed in Lemma 4.1 will be required in our proof.
Lemma 4.2. Let L : {−1, 1}n → R be the separating function of degree D given by Lemma 4.1. Let
h : {−1, 1}n → R>0 be a non-negative junta that depends only on variables T ⊆ [n] and let S be any subset of
[n] such that and |S| + |T| 6 D. Then,
E[LhχS ] 6 E[Lh].

13

Proof. Note that h(1 − χS ) is a non-negative D-junta. Therefore, hL, h(1 − χS )i > 0; the claim follows.

We are now ready to prove Lemma 4.3 which can be seen as a robust version of the property
that E[L h] > 0 for every non-negative D-junta h.
Lemma 4.3. Let L be a separating function of degree D = 4d as in Lemma 4.1. Then, for any non-negative
d-junta c with kck∞ 6 1, and any (1/n4 )-decaying function h, E[Lc(1 + h)] > −n−8d .
P
P
Proof. Write h = hlow + hhi1h where hlow = |S|6D−d b
h(S)χS , and hhi1h = |S|>D−d b
h(S)χS .
We have:
E[Lc(1 + h)] = E[Lc(1 + hlow )] + E[Lchhi1h ].
Let ε = 1/n4 . Now, Lc is of degree at most (D + d) and kLck∞ 6 nD . Further, for any x,
X
X
b
|hhi1h (x)| = |
h(S)χS (x)| 6
ε|S|
6

S:|S|>D−d
n
X
`

S:|S|>D−d

ε · n`

`=D−d

6 2(εn)D−d ,
where the last inequality follows as εn = 1/n3 < 1/2. Therefore, khhi1h k∞ 6 2(εn)D−d and
| E[Lchhi1h ]| 6 kLck∞ · khhi1h k∞ 6 2n2D−d · εD−d .

(4.1)

Next, note that hlow is a linear combination of parities of degree at most d and that c is a function
of degree at most d. Thus, by Lemma 4.2, we have,
X
| E[Lchlow ]| 6
|b
h(S)|| E[LcχS ]|
|S|6D−d

X

6

|b
h(S)| E[Lc].

|S|6D−d

Since by definition E[h] = 0, we have:
E[Lc(1 + hlow )] > E[Lc](1 −

X

ε|S| ) > E[L c](1 − 2Dnε).

(4.2)

16|S|6D−d

Using that ε < 1/n4 and D < n, we have E[Lc(1 + hlow )] > 0. Using (4.1) and (4.2),
E[Lc(1 + h)] > −2ε3d n7d > −n−8d .

Finally, we can complete the proof of Lemma 2.4.

14

Proof of Lemma 2.4. Fix η = n1 . For the sake of contradiction, assume that deg+ ( f + η) > 8d. Consider
the functional L given by Lemma 4.1 with D = 4d.
Since f is an (ε, δ)-approximate d-junta, we have
X
f (z) =
λi ci (z)(1 + hi (z)) + γ(z)
i

where the functions hi are ε-decaying and the function γ satisfies E[|γ|] 6 δ. Now, take inner
products with L on both sides of the above equation. On one side, we get
E[L · f ] 6 −η .
On the other side, we get
X
i



X  1
λi E[L ci (1 + hi )] + E[L γ] > − 
λi  · 8d − kLk∞ E[|γ|]
n
i
>−

1
− n4d n−8d > −η ,
n8d

yielding a contradiction.

5



The Junta Approximation Theorem

Here we prove Theorem 2.7 assuming Theorem 2.10. In addition to the latter decomposition, the
proof relies on certain extractor properties of the inner-product function. Concretely, we need the
following statement about the distribution of G(X, Y) for blockwise-dense random variables X, Y
that is implicit in [GLM+ 15].
Lemma 5.1. Fix q = 2b for b > 50 and identify [q] with {−1, 1}b . Let 1 : {0, 1}b × {0, 1}b → {−1, 1} be the
Boolean inner product function.
Suppose X and Y are independent, blockwise-dense random variables on [q]n . Let ν be the density of the
random variable 1⊗n (X, Y) on {−1, 1}n . Then, ν = 1 + h for an an ε-decaying function h where ε = 2−0.5b .
The lemma is an easy consequence of the fact that the inner-product function is a two-source
extractor for sufficiently high-entropies:
Fact 5.2 (Chor-Goldreich [CG88]). Suppose X, Y are independent random variables over {−1, 1}` for ` > 7
with min-entropy H∞ (X), H∞ (Y) > 0.8`. Let h : {0, 1}b × {0, 1}b → {−1, 1} be the Boolean inner product
b
function defined by h(X, Y) = (−1)⊕i=1 Xi ·Yi . Then,
| E[h(X, Y)]| 6 2−0.6`+1 .

15

Let X0 , Y0 be the random variables in [q/2]n obtained by removing the first bit in each block - i.e.
by identifying [q/2] with {−1, 1}b−1 . Then, since X, Y are independent and blockwise-dense, for each
i, Xi0 , Yi0 are independent random variables with min-entropy H∞ (Xi0 ), H∞ (Yi0 ) > 0.8` − 1. Applying
Fact 5.2 to Xi0 and Yi0 , we obtain that k E[h(Xi0 , Yi0 )]| 6 2−0.6`+3 .
By expanding out E[1(Xi , Yi )] by fixing each of the 4 values for the first bits in Xi , Yi and using
the upper bound above, we obtain that
k E[1(Xi , Yi )]k 6 4 · 2−0.6`+3 = 20.6`+5 .

(5.1)

Proof of Lemma 5.1. By Fact 5.2, for any S ⊆ [n] we have
b
ν(S) = E[ν(z)χS (z)] = E [χS (z)] = E[Πi∈I 1(X{i} , Y{i} )] = E[1(XS , YS )].
z∼ν

Here, XS = i∈S X{i} and YS = i∈S Y{i} .
Thus, using (5.1), |b
ν(S)| 6 2−0.6b|S|+5|S| < 2−0.5b|S| for b > 50.
P
ν(S)χS (z). Then, ν = 1 + h and by the above estimate, h is ε-decaying for
Let h(z) = |S|>1 b
ε = 2−0.5b .

Q

Q

Lemma 5.1 showed that if X, Y are blockwise-dense random variables, then the density of
is an ε-decaying perturbation of the uniform density. In the following, we show a
refinement of Lemma 5.1 when X, Y are aligned d-CBD random variables - specifically, that 1⊗n (X, Y)
is a an ε-decaying perturbation of a non-negative d-junta.
1⊗n (X, Y)

Lemma 5.3. Let X, Y be aligned d-CBD random variables over ({0, 1}b )n for b > 7 with the aligned blocks
I ⊆ [n] and XI = α, YI = β. Let ν be the density of z = 1⊗n (X, Y). Then, for ε = 2−0.5b , there exists an
ε-decaying function h such that
ν = 1[zI = 1⊗|I| (α, β)] · (1 + h).
In particular, if u, v are aligned d-CBD densities over ({−1, 1}b )n , then Accu,v is a (2−.5b , 0)-approximate
conical d-junta.
Proof. Let Z = 1⊗n (X, Y). Then, ZI = 1⊗I (α, β and ZI = 1⊗|I| (XI , YI ). In particular, the density of Z can
be written as νI · νI where νI is the density of ZI and νI the density of ZI .
Now, by definition, XI , YI are d-CBD random variables. Thus, by Lemma 5.1, the density νI of
ZI can be written as 1 + h for a 2−0.5b -decaying function. This completes the proof of the first part of
the statement. The next part follows from the definition of Accu,v .

We are now ready to prove Theorem 2.7 which we restate for convenience.
Theorem (Restatement of Theorem 2.7). There exists a constant α2 > 1 such that the following holds.
Let u, v be densities over [q]n with q = 2b such that H∞ (u) + H∞ (v) > 2b(n − t). Then, for all b > α2 log n
and d > α2 t, Accu,v {−1, 1}n → R>0 is a (2−0.5b , (2−0.5b )d )-approximate conical d-junta.
Proof. We apply Theorem 2.10 to u, v to write
u⊗v=

N
X

λi ui ⊗ vi + λerr γerr ,

i=1

16

as guaranteed by the theorem. Then,
Accu,v =

N
X

λi Accui ,vi + λerr γ(z),

i=1

where γ denotes the distribution of G(X, Y) for (X, Y) ∼ Derror . Now, as ui , vi are aligned d-CBD
densities, by Lemma 5.3 each Accui ,vi is a (2−.5b , 0)-approximate conical d-junta. Hence, Accu,v is a
(2−.5b , λerr )-approximate conical d-junta. The claim now follows from the bound on λerr .


6

Decomposition of High Min-Entropy Distributions

In this section we prove Theorem 2.10. In fact, we show a stronger decomposition theorem that is
no more difficult to prove and is needed to recover the results of [GLM+ 15] in our framework. We
will use the following notation:
• We use distributions, densities and random variables interchangeably with the meaning being
clear from the context.
• For µ a density on some domain D and S ⊆ D, we write µ|S for the density µ conditioned on
S. We also define µ(S) = PrX∼µ [X ∈ S].
• For a random variable X on [q]n and I ⊆ [n], we write XI to denote X projected to the
coordinates in I. For a density µ on [q]n × [q]n and I ⊆ [n], we write µI to denote the density
on [q]|I| × [q]|I| obtained by projecting µ to the cooridnates in I.
• For brevity, we say a density µ on [q]n × [q]n is an aligned d-CBD if its two marginals along
[q]n are aligned d-CBD densities.

6.1

Warm Up: One-Dimensional Decompositions

Observe that by definition, any d-CBD density has min-entropy at least 0.8 log q(n − d) which
for d  n, we consider high. Thus, any convex combination of d-CBD densities also has high
min-entropy. One could ask for a converse at this point: can every high min-entropy density be
written as a convex combination of d-CBD densities for small d? As a warmup for the more general
decomposition, we first show that this is indeed the case.
Lemma 6.1. Let µ is a density on [q]n with H∞ (µ) > (n − t) · log q. Then, there exists a partition of [q]n as


 [ 


[q]n = 
Si  ∪ Serror


i∈[N]

such that
• For each i ∈ [N], µ|Si is a 10t-CBD distribution.
17

• µ(Serror ) 6 q−t .
Proof. We present an algorithm that obtains the claimed partition.
Setup: µ is a distribution over [q]n with H∞ (µ) > (n − t) · log q.
Decompose(S)
Input S ⊆ [q]n .
1. If µ|S is blockwise-dense , Terminate and return S.
2. If µ(S) 6 q−t , Terminate and return S, labeled as Serror .
3. Else, let Y ∼ µ|S . Let I ⊆ [n] be a maximal set such that H∞ (YI ) < 0.8 log q · |I| and suppose
α ∈ [q]I be such that p = Prµ|S [YI = α] > q−0.8|I| . Then, set S1 ← S ∩ {y ∈ [q]n : yI = α} and
S2 ← S ∩ {y ∈ [q]n : yI , α}.
4. Return S1 ∪ Decompose(S2 ).
To get the desired decomposition of µ, we call Decompose([q]n ). Before we analyze the decomposition
so produced, let us consider a single execution of the subroutine. Consider an execution of
Decompose(S) that terminates in Step 4, returning a subset S1 and calling Decompose(S2 ). We make
the following observations.
Claim 6.2. µ|S1 is blockwise-dense except for the fixed coordinates in I.
Proof. Since I is a maximal set such that H∞ (YI ) < 0.8 log q|I|, for any subset J ⊆ [n]/I, we have
H∞ (Y J |YI = α) > 0.8 log q|J|.

Claim 6.3. |I| 6 10t
Proof. For any β ∈ [q]|I| ,
P [YI = β] =

µ|S

6
6

Pµ [YI = β]
µ(S)
Pµ [YI = β]

(Step(2) did not terminate)

q−t
qt−|I|
= q2t−|I|
q−t

(H∞ (µ) > (n − t)(log q))

Since there exists α ∈ [q]I such that Pµ|S [YI = α] > q−0.8|I| , we get that q−0.8|I| 6 q2t−|I| . This implies
that |I| 6 10t.

From the above claims, it is clear that µ|S1 is a 10t-CBD distribution, whenever Decompose(S)
terminates in Step (4).

18

Suppose we call Decompose([q]n ), the recursive algorithm will return a partition of [q]n into
subsets {Si }i∈[N] and eventually terminate either via Step(1) or Step(2). If the algorithm terminates
via Step (1), then µ|Si is 10t-CBD for all the sets Si and the lemma follows. If the algorithm terminates
via Step (2), then it produces a subset Serror with µ(Serror ) 6 q−t , as desired.


6.2

Rectangular Decompositions

To prove our junta theorem, Theorem 2.7, and for other plausible applications in communication
complexity, the decomposition obtained by Lemma 6.1 does not suffice. In particular, the underlying
domain is two-dimensional [q]n × [q]n , and the partitions need to be rectangular. In this section,
we will prove a general rectangular decomposition theorem designed for distributions with high
min-entropy.
A combinatorial rectangle R ⊆ [q]n × [q]n is given by R = A × B for A, B ⊆ [q]n . We can now
state our main decomposition theorem.
Theorem 6.4 (Rectangular Decompositions). Let µ be a probability density on [q]n × [q]n such that for
all I ⊆ [n],
H∞ (µI ) > 1.9 · log q · |I| − t .
Then for all d ∈ N, there exists a partition


 [ 


[q]n × [q]n = 
Ri  ∪ Error


i∈[N]

where {Ri = Ai × Bi }i∈[N] are rectangles such that
1. For each i ∈ [N], (Xi , Yi ) ∼ µ|Ri , Xi , Yi are aligned d-CBD.
2. µ(Error) 6 2t · (dq−0.05 )d
Notice that the above theorem also implies that the density µ can be approximated by a convex
combination of aligned d-CBD distributions by setting,
X
µ=
µ(Ri ) · µ|Ri + µ(Error) · µ|Error .
i∈[N]

Theorem 2.10 is an an immediate consequence of the above decomposition theorem.
Proof of Theorem 2.10. Let µ be the density u ⊗ v on [q]n × [q]n . Then, µ for all I ⊆ [n], H∞ (µI ) >
2(log q)|I| − t. Now, apply Theorem 6.4 to obtain a partition of [q]n × [q]n as ∪i∈N Ri ∪ Error satisfying
the conditions of the theorem. Then,
µ=

N
X

µ(Ri ) · µ|Ri + µ(Error)µ|Error .

i=1

P
Note that N
i=1 µ(Ri ) + µ(Error) = 1. Let Ri = Ai × Bi . Then, we can write µ|Ri = ui ⊗ vi , where
ui = u|Ai and vi = v|Bi . Then, Xi ∼ ui , Yi ∼ vi are aligned d-CBD and
µ(Error) 6 2t (dq−0.05 )d 6 2−t (nq−0.05 )d 6 2−t q−Ω(d) 6 q−Ω(d) ,
for q > nc , d > ct for a sufficiently big constant c > 1. This proves the theorem.
19



6.3

The Decomposition Algorithm

We will show Theorem 6.4 by devising an algorithm that constructs the partition given the
distribution µ and a parameter d ∈ N. The algorithm is an natural extension of the one used in the
proof of Lemma 6.1 and is similar to the one used in [GLM+ 15]; however, our analysis is quite
different from theirs. Indeed, while they also obtain a similar decomposition theorem, the error
guarantee is not exponentially small as we obtain and is needed in our application.
The formal description of the algorithm is at the end of this subsection. For exposition, we
depict a labeled execution tree of the algorithm Figure 1. Decompose is the main procedure that
takes as input a rectangle A × B ⊆ [q]n × [q]n . This rectangle will always satisfy the invariant of
having an aligned set of nodes fixed - i.e. there is an explicitly identified set of indices F ⊆ [n] such
that for some two fixed strings α, β, for all (x, y) ∈ A × B, xF = α and yF = β. Observe that in the
beginning, A = B = [q]n and F = ∅.
Each time Decompose is invoked by the algorithm, we create a new node in the execution tree
and identify it as being created by Decompose by indexing it with v1 , v2 , . . . ,. If the set of fixed
blocks F in the input rectangle R has size > d, the algorithm terminates and adds the associated
rectangle R to Errorb ; Errorb contains the set of rectangles that account for error owing to the number
of fixed blocks in them exceeding d. Next, if µ(R) < δ, then R is added to Errora ; Errora maintains
the collection of rectangles that are labeled as error because their measure was too small.
Now, suppose that the input rectangle R does not satisfy the conditions of Errora or Errorb .
If µ|R is blockwise-dense , then, we terminate the algorithm and return R. Otherwise, there
exists S ⊆ [n] and some assignment to variables in S, say αS such that Pµ|R [XS = αS ] > q−0.8|S| (or
Pµ|R [YS = αS ] > q−0.8|S| ). The idea is to split the rectangle A × B into two rectangles, A|S=αS × B and
A|S,αS × B; here, we define A|S=αS denotes the set,
A|S=αS = A ∩ {x : xS = αS } and A|S,αS = A ∩ {x : xS , αS } .
In the rectangle A|S=αS × B, X and Y don’t have the same set of fixed blocks, since X is fixed in
F ∪ S while Y is fixed only on F. To remedy this, the subroutine XDecompose (or YDecompose ,
respectively) is executed on the rectangle A|S=αS × B. The Decompose routine continues with the
remaining rectangle A|S,αS × B. Each call to XDecompose or YDecompose is denoted by a node in
the execution tree labeled by w1 , w2 , . . . .
The subroutine XDecompose (the case of YDecompose is analogous) takes as input the rectangle
A × B along with the fixed set F that was the current input of the Decompose routine when
XDecompose was invoked in addition to the new set of indices S that violated blockwise-density.
XDecompose then chooses every possible value β for YS and for each β, calls Decompose recursively
with the rectangle A × B|S=β with F ∪ S as the set of fixed coordinates.

20

Decomposition Algorithm

Setup:
• A probability density µ such that H∞ (µ|I ) > 1.9 log q · |I| − t for all I ⊆ [n].
def

• A parameter d ∈ N and let δ = q−0.05d . Set Errora = Errorb = ∅.
Decompose(A × B, F)
Input: A rectangle A × B ⊆ [q]n × [q]n , F ⊆ [n]: subset of “fixed” indices.
Invariant: AF , BF are fixed.
1. If |F| > d, Terminate after setting Errorb ← Errorb ∪ A × B.
2. Set R ≡ R0 ≡ A × B.
3. While µ(R) > δ · µ(R0 ) do
(a) Let (X, Y) ∼ µ|R . If XF , YF are blockwise-dense , Terminate.
(b) Else, if there is an S ⊆ [n]\F and α ∈ [q]S such that
P[XS = α] > q−0.8|S| ,
call YDecompose on input (A|S=α , B, F, S) and set R ← A|S,α × B
(c) Else, if P[YS = α] > q−0.8|S| then call XDecompose on input (A, B|S=α , F, S) and set
R ← A × B|S,α .
4. Set Errora ← Errora ∪ R.
XDecompose(A × B, F, S)
Input: A rectangle A × B, F ⊆ [n]: common subset of “fixed” indices; S: the set of coordinates newly
fixed in A (but not in B).
Invariant: XF and YF∪S are fixed.
1. For every β ∈ [q]S , Decompose(A|S=β , B, F ∪ S).
YDecompose(A × B, F, S)
Input: A rectangle A × B, F ⊆ [n]: common subset of “fixed” indices.
S: the set of coordinates newly fixed in B (but not in A).
Invariant: XF∪S and YF are fixed.
1. For every β ∈ [q]S , Decompose(A, B|S=β , F ∪ S).

6.4

Analysis: Proof of Theorem 6.4

We now analyse the algorithm.

21

𝒜×ℬ
𝒜%&' × ℬ, F, S

𝒜%)',-&. × ℬ, F, T

𝒜%()'(,%+)'+,… × ℬ-( ).(,-+).+ ,…

BD or “too small”

𝒜%&' × ℬ%&'/, 𝐹 ∪ 𝑆

BD or “too deep”
Figure 1: Execution Tree: Black Nodes are Calls of Decompose , Green Nodes are calls of XDecompose or YDecompose .
“too deep" ≡ Errora , “too small” ≡ Errorb and BD = blockwise-dense

Execution Tree. Consider the execution tree of the decomposition algorithm (Figure 1). We
associate a node ρ corresponding to a call of Decompose with parameters Aρ , Bρ and Fρ for
Aρ , Bρ ⊆ [q]n and Fρ ⊆ [n]. Nodes ρ corresponding to a call of XDecompose or YDecompose are
associated with an additional parameter Sρ ⊆ [n]. The calls of Decompose and XDecompose or
YDecompose alternate.
Before we analyze the decomposition, we introduce some notation.
• For each vertex ρ, let µ(ρ) = µ(Aρ × Bρ ). Let R(ρ) denote the rectangle Aρ × Bρ .
• For a child b of a vertex a, let µ(b|a) = µ(b)/µ(a).
• We will reserve the letter v (and various suffixes) for nodes corresponding to calls of
Decompose (i.e., the vertices in odd-layers) and the letter w for nodes corresponding to calls
of XDecompose or YDecompose (i.e., the vertices in even-layers).
• For a vertex v let Cv = (w1 , . . . , wcv ) be the children of v (in the order they were generated),
where we assume that w1 , . . . , wcv −1 lead to recursive calls of XDecompose or YDecompose
while wcv corresponds to the rectangle marked as Errora in Step(4) of Decompose .
• For a vertex v, and wi ∈ C(v), let Swi ⊆ [n] denote the corresponding set of new blocks that
were fixed to produce wi .
22

• We say a node v in the tree is bad if |Fv | > 2d but µ|Av ×Bv is not blockwise-dense in the
non-fixed blocks. A root-to-leaf path v1 , w1 , v2 , w2 , . . . , vt , wt , vt+1 is called a bad path if vt+1 is
bad.
Note that the tree yields a partition of [q]n × [q]n as,



 [


[q]n × [q]n = 
R(v) ∪ Errora ∪ Errorb ,


v∈L]

where L denotes the leaves of the tree not added to Errora or Errorb . We will show that this partition
satisfies the conditions of the theorem when we take Error = Errora ∪ Errorb . Note that, all the leaves
in the execution tree correspond to the calls of Decompose .
We first argue that µ|R(v) for v ∈ L gives d-CBD densities in the non-fixed coordinates.
Lemma 6.5 (Good Rectangles). Let v ∈ L. Then, µ|R(v) is an aligned d-CBD.
Proof. The assumptions imply that |Fv | 6 d. Further, as R(v) was not added to Errora , R(v) is a leaf
because for (X, Y) ∼ µ|R(v) , XF , YF are blockwise-dense . Thus, µ|R(v) is an aligned d-CBD density.

It is also easy to bound µ(Errora ):
Lemma 6.6. µ(Errora ) 6 dδ.
Proof. Note that each call of Decompose leads to at most one rectangle being added to Errora .
Further, if Decompse(R0 ) led to adding a rectangle R ⊆ R0 to Errora , then µ(R) < δ · µ(R0 ). Now, in
any single layer of the execution tree the nodes corresponding to calls of Decompose are associated
with disjoint rectangles. Thus, the total measure of all the rectangles that are included in Errora due
to Decompose calls from nodes in a specific layer is at most δ. As there are at most d layers that
have Decompose nodes, it follows that µ(Errora ) 6 dδ.

The main task is to prove an upper bound on µ(Errorb ).
Bounding µ(Errorb ). We begin with an important definition.
Definition 6.7 (θ(wi | v)). For a node v associated with a Decompose call, let Cv = (w1 , . . . , wcv ) be
the children of v. Define
cv
X
θ(wi | v) =
µ(w j | v).
j=i

Intuitively, θ(wi | v) denotes the relative measure of the rectangle R inside Step 4 of Algorithm
6.3 just before the call of XDecompose or YDecompose associated with the node wi .
Lemma 6.8. Fix any vertex v and a child w of v,
µ(w|v) > q−0.8|Sw | · θ(w|v).
23

Proof. Let R be the rectangle processed in the while loop inside the call of Decompose associated
with v just before the call to create w. Suppose that w was created by a recursive call to XDecompose
for Sw ⊆ [n] such that P(X,Y)∼µ|R [XSw = α] > q−0.8|Sw | (the case of a call to YDecompose can be dealt
with analogously). Thus, µ|R (R(w)) > q−0.8|Sw | .
Now, we can write µ(w|v) as a product of the relative probability of R in R(v) and the relative
probability of R(w) under R. Concretely,
µ(w|v) = µ|R(v) (R(w)) = µ|R(v) (R) · µ|R (R(w)) = θ(w|v) · µ|R (R(w)) > θ(w|v) · q−0.8|Sw | ,
where the last equality follows from the definition of θ(w|v).

Next, we estimate µ(v) for every v that is a bad leaf i.e., a leaf at depth 2d + 1. We begin by
showing a bound on µ(v) for an arbitrary node v.
Lemma 6.9. For any vertex v in the execution tree,
µ(v) 6 2t · q−1.9|Fv | .
Proof. The rectangle R(v) corresponding to v has the blocks Fv fixed, while the values in the
remaining blocks could also be constrained. Let us suppose XFv = α and YFv = β for (X, Y) ∈ R(v).
By our assumption on µ,
H∞ (µ|Fv ) > 1.9 · log q · |Fv | − t ,
which implies that,
µ(v) 6 P[XFv = α ∧ YFv = β] 6 2−H∞ (µFv ) 6 2t · q−1.9|Fv | .
µ


Lemma 6.10. Let v1 , w1 , . . . , v` , w` , v`+1 be a bad path ending at a node that is added to Errorb . Then,
µ(v`+1 ) 6 q−1.1|Fv`+1 | · 2t ·

Ỳ µ(wi |vi )
i=1

θ(wi |vi )

Proof. Let s = |Fv`+1 |; then, by Lemma 6.9,
µ(vd+1 ) 6 q−1.9s · 2t
On the other hand, we know that
µ(v`+1 ) =

Ỳ

P`

i=1 |Swi |

= s. Thus, by Lemma 6.8,

µ(vi+1 |wi )µ(wi |vi ) >

Ỳ

µ(vi+1 |wi ) · θ(wi |vi ) · q−0.8|Swi | .

i=1

i=1

The above two inequalities imply that,
Ỳ

µ(vi+1 |wi )θ(wi |vi ) 6 q−1.1s · 2t .

i=1

24

The claim now follows from the above inequality along with


Ỳ
Ỳ
 Ỳ µ(wi |vi )
.
µ(v`+1 ) =
µ(vi+1 |wi )µ(wi |vi ) = 
µ(vi+1 |wi )θ(wi |vi ) ·
θ(wi |vi )
i=1

i=1

i=1


We need the following elementary lemma.
P
Lemma 6.11. Let a1 , . . . , aN ∈ (0, 1) be such that N
i=1 ai = 1 and aN−1 + aN > ε. Then,
N
X

aj
P

j=1

6 dlog(1/ε)e + 2.

i>j ai

Proof. For i < N, let si = j>i a j ; clearly, si is a decreasing sequence and sN−1 > ε. Let `i be the largest
P
index such that s`i = Nj=`i a j > 21i .
By definition,
`i+1
N
X
X
1
aj 6
aj < i
2
j=` +1
j=` +1
P

i

i

Let t = dlog(1/ε)e. Clearly, `t > N − 1. Now, we have,
N−1
X
i=1

`i+1
t
ai X X a j
=
si
sj
i=0 j=`i +1
P`i+1
t
a
X
j=`i +1 j
6
s`i+1

6

i=0
t
X

1 = t + 1.

i=0


We have the following immediate consequence of the above lemma.
Corollary 6.12. For every vertex v,
X µ(w|v)
6 dlog(1/δ)e + 2.
θ(w|v)

w∈Cv

P
Proof. Let Cv = (w1 , . . . , wcv ). Then, θ(wcv−1 |v) = µ(wcv−1 |v) + µ(wcv |v) > δ. As θ(wi |v) = j>i µ(w j |v),
the claim now follows by applying the previous lemma to the numbers µ(w1 |v), µ(w2 |v), . . . , µ(wcv |v).

Lemma 6.13. The sum over all leaves
X
paths v1 ,w1 ,...,w`−1 ,v`

q−|Fv` |

Ỳ µ(wi |vi )
i=1

θ(wi |vi )

25

6 dlog 1/δe + 2

d

Proof. For each v corresponding to a Decompose call, define a probability distribution γ( |v) over Cv
as follows: for each w ∈ Cv ,

−1
µ(w|v)  X µ(w|v) 
 .
γ(w|v) =
· 
θ(w|v) 
θ(w|v) 
w∈Cv

For each w corresponding to a XDecompose or YDecompose call consider the uniform distribution over the children of w. Then, these distributions induce a probability distribution over the
Q
leaves of the execution tree: the probability of any leaf v`+1 is given by `i=1 q−|Swi | · γ(wi |vi ), where
v1 , w1 , . . . , v` , w` , v`+1 is the path from the root to v`+1 .
By our construction, the total probability under the above distribution of all the leaves is 1.
Thus, the sum over all leaves
X

Ỳ

q−|Swi | · γ(wi |vi ) = 1.

paths v1 ,w1 ,...,v` w` i=1

By Corollary 6.12, γ(wi |vi ) >

µ(wi |vi )
θ(wi |vi )

1
. The result follows from substituting this into
(dlog 1/δe+2)
the previous expression and using the fact that ` 6 d (number of fixed coordinates is at most d). 

·

We are now ready to bound µ(Errorb ).

Lemma 6.14. µ(Errorb ) 6 q−0.1d · 2t · dlog 1/δe + 2 d .
Proof. Let Bad denote all leaves that resulted in rectangles being added to Errorb . The proof follows
by using Lemmas 6.10 and Lemma 6.13. For brevity, in the following, let v1 , w1 , . . . , v` , w` , v`+1 = v
be the path to v from the root.
X
v∈Bad

µ(v) 6

X

q−1.1|Fv | · 2t ·

Ỳ µ(wi |vi )

θ(wi |vi )
i=1


Ỳ µ(wi |vi ) 
 X
 6 q−0.1d · 2t · dlog 1/δe + 2d .
q−|Fv | ·
6 q−0.1d · 2t 

θ(wi |vi ) 
v∈Bad

v∈Bad

i=1


Proof of Theorem 6.4. One executing Algorithm 6.3, we obtain a partition of [q]n ×[q]n into ∪v∈L R(v)∪
Error, where we define Error = Errora ∪ Errorb .
By Lemma 6.5, µ|R(v) is an aligned d-CBD for each v ∈ L. Furthermore, the total measure of
Error is
µ(Error) = µ(Errora ) + µ(Errorb )

6 dδ + q−0.1d · 2t · dlog 1/δe + 2 d ,
6 2t · (dq−0.05 )d

(Lemma 6.6 and Lemma 6.14)

( for δ = q−0.05d ).

This completes the proof.


26

7

Non-negative Rank and LP Lower Bounds for CSPs

In this section, we show that proving a lower bound on the size of linear programming relaxations for
CSPs reduces to proving non-negative rank lower bound on a pattern matrix M f for an appropriate
choice of f . We then use this characterization to prove Theorem 1.2, Corollary 1.3. We first show
the following.
Lemma 7.1 (LP Lower Bounds from Pattern Matrices). Let 0 < s < c 6 1 and let Λ : {−1, 1}k → {0, 1} be
a predicate and let I∗ be an instance of CSP(Λ) on n variables such that opt(I∗ ) 6 s and let f (x) = c − I∗ (x).
For all 1 : [q]×[q] → {−1, 1}, any linear programming relaxation of CSP(P) that achieves (c, s)-approximation
1
on instances with q · n variables, has size at least R > Ω(rank+ (M f )).
The above lemma is an easy consequence of the characterization of size of linear programs for
CSPs [CLRS13, Yan88]. Towards stating the characterization, let us fix a CSP Λ. For n ∈ N and
s ∈ [0, 1], let Λsn denote the family of all instances of the CSP on n variables with opt(I) 6 s. With
these definitions, we are ready to state the characterization.
Fact 7.2. [CLRS13] The size of the smallest linear program that (c, s)-approximates a CSP Λ on instances
with n variables is Θ(rank+ (Mn,s )) where the matrix Mn,s : Λsn × {−1, 1}n → R is defined as
def

Mn,s (I, x) = c − I(x) .
1

To prove Lemma 7.1, we will show that M f is a sub-matrix of Mq·n,s , and therefore rank+ (Mq·n,s ) >
rank+ (M f ). By Fact 7.2, this implies that the size of any LP that (c, s)-approximates the CSP on
instances with q · n is at least rank+ (M f ). Hence, Lemma 7.1 is an immediate consequence of the
following.
Lemma 7.3. Let I∗ be an instance of CSP on n variables such that opt(I∗ ) = s and let f (x) = c − I∗ (x).
1
Let 1 : [q] × [q] → {−1, 1} be a gadget function. Then, M f is a sub-matrix of Mq·n,s .
Proof. For α ∈ [q], define its 1-encoding 1 ◦ α ∈ {−1, 1}q consisting of the truth-table of the function
def

1 ◦ α : β → 1(α, β). Specifically, if we index the coordinates of 1 ◦ α with β ∈ [q], then (1 ◦ α)β = 1(α, β).
Similarly for x ∈ [q]n , define x̃ ∈ {−1, 1}q·n by setting x̃i := 1 ◦ xi .
For each y ∈ [q]n , we create an instance I y on N = q · n variables. We will index the variables of
I y by [n] × [q] and denote them by {zi,β |i ∈ [n], β ∈ [q]}. The instance I y is obtained by planting the
instance I∗ on the subset of variables {z1,y1 , . . . , z1,yn }.
1
By definition of the matrices M and M f , we conclude that for any x, y ∈ [q]n ,
Mq·n,s (I y , x̃) = c − I y (x̃) ,


= c − I∗ x̃1,y1 , . . . , x̃1,yn ,


= c − I∗ (1 ◦ x1 ) y1 , . . . , (1 ◦ xn ) yn ,

= c − I∗ 1(x1 , y1 ), . . . , 1(xn , yn ) = f (1n (x, y)) ,
1

= M f (x, y) .
1

Therefore, the matrix M f is a sub-matrix of Mq.n,s as desired.
27



Now we are ready to wrap up the proof of our main result Theorem 1.2, concerning the
optimality of Sherali-Adams linear programs, among all linear programs of roughly the same size.
Proof of Theorem 1.2. Suppose f (n)-round Sherali-Adams relaxation for a CSP Λ does not achieve a
(c, s)-approximation on instances with n variables. This implies that there exists instances In on n
variables such that opt(I) 6 s but the optimum value of f (n)-round Sherali-Adams linear program
optSA( f (n)) (I) > c.
Set In (x) := c − n1 − In (x). The work of Chan et al. [CLRS13] observes that the dual to the
f (n)-round Sherali-Adams linear program corresponds to expressing the function c − In (x) as a
sum of non-negative f (n)-juntas. In particular, this implies that deg+ (In + n1 ) > f (n).
Applying Theorem 1.7 to function hn we get that,
rank+ (MbIn ) > 2Ω(b·deg+ (hn + n ))
1

for some b = Θ(log n). By Lemma 7.3, the matrix MbIn is a sub-matrix Mn·q,s for q = 2b . Therefore we
get,
1
rank+ (MnH ,s ) > nh·deg+ (In + n ) > nh· f (n) ,
for some constants h, H ∈ N. Using Lemma 7.1, this implies that no linear program of size nh· f (n)
can (c − n1 , s)-approximate the CSP Λ on instances with nH variables.

We now prove Theorem 1.2, Corollary 1.3. For this, we need the following results on the
performance of the Sherali-Adams hierarchy for CSPs. Charikar et. al. [CMM09] showed the
following lower bound for MAX-CUT.
Theorem 7.4 (Sherali Adams Integrality Gaps [CMM09]). For every ε > 0, there is a γ = γ(ε) such that
the nγ -round Sherali-Adams relaxation for MAX-CUT does not achieve a (1/2 + ε, 1 − ε)-approximation7 .
Grigoriev [Gri01] showed a lower bound for the Sum-of-Squares SDP hierarchy (that is a
strengthening of the Sherali-Adams LP hierarchy and thus the lower bounds carry over) for 3XOR;
Schoenebeck [Sch08] rediscovered this result and also observed that it implies a similar lower bound
for the MAX-3SAT problem. Following this, [BGMT12] extended this result to show a Ω(n)-round
lower bound for every pairwise independent CSP; here, a CSP defined by a predicate P : {0, 1}k → {0, 1}
is pairwise independent if there exists a balanced pairwise independent distribution µ supported
on P−1 (1)).
Theorem 7.5 ([Gri01, Sch08, BGMT12]). For every k-ary pairwise independent predicate P and ε > 0,
there exists a constant c = c(k, ε) such that the cn-round Sherali-Adams relaxation for MAX-CSP problem on
predicate P achieves a (|P−1 (1)|/2k + ε, 1 − ε)-approximation. As a corollary, for some constants c1 (ε), c2 (ε),
the c1 (ε)-round Sherali-Adams relaxation for MAX-3SAT does not achieve a (7/8 + ε, 1 − ε)-approximation,
and c2 (ε)-round Sherali-Adams relaxation for MAX-3XOR does not achieve a (1/2 + ε, 1 − ε)-approximation.
7
The results of [CMM09] are actually stated in terms of integrality gaps, but their proofs actually show this stronger
statement.

28

Proof of Corollary 1.3. Consider the case of MAX-3SAT. Then, combining the above theorem with
Theorem 1.2 we get that any LP relaxation for MAX-3SAT of size nhc1 (ε)n on nH -variables does not
achieve a (7/8 + ε, 1 − ε)-approximation. Let N = nH . Then, this says that no LP relaxation for MAX1/H
1/H
3SAT of size Nhc1 (ε)N /H = NΩε (N ) achieves a (7/8 + ε, 1 − ε)-approximation. The latter condition
in particular implies that such LP relaxations have integrality gap at least 1 − ε/(7/8 + ε) = 8/7 − O(ε).
This implies the claimed lower bound for MAX-3SAT. The claims for MAX-3XOR, MAX-CUT, and
pairwise independent predicates follow similarly.

Proof of Theorem 1.8. We only sketch the argument here and refer to [CLRS13] where the connection
between such separations and lower bounds for CSPs as above is drawn out in more detail.
The theorem essentially follows by showing corresponding separations for degrees and using
our lifting theorem. Let f : {−1, 1}n → R>0 be a function and let deg( f ) be the degree of f as a
polynomial and for all δ > 0, let
degδ+ ( f ) = min{deg+ (h) : kh − f k∞ 6 δk f k∞ }.
δ
n 
n 
b·deg( f ) , rankδ (Mb ) 6
Then, for all b, rank(Mbf ) 6 deg(
· 2b·deg+ ( f ) . Thus, to show the
+
f) · 2
degδ+ ( f )
f
theorem, it would suffice to find a function f : {−1, 1}n → R>0 such that E[ f ] = Ω(1), deg( f ) = O(1),
degε+ ( f ) = O(log(1/ε)) and deg+ ( f + ε) = Ωε (n). For, if we take M = Mbf for b > C log n as in

N×N for N = 2bn and
Theorem 1.7, then M ∈ R>0

!
n
rank(M) 6
· 2b·deg( f ) = (log N)O(1)
deg( f )
!
ε
n
ε
rank+ (M) 6
· 2b·deg+ ( f ) = nO(log(1/ε) = (log N)O(log(1/ε)) ,
ε
deg+ ( f )
rank+ (M) = exp(Ω(b · deg+ ( f + O(1/n)))) = exp(Ω(b · deg+ ( f + ε))) = NΩε (1) .
To show the existence of such a function, let I be an instance of MAX-3SAT on n-variables
such that opt(I) 6 7/8 + ε, but the Ωε (n)-round Sherali-Adams relaxation has value at least 1 − ε.
Such instances exist by [Gri01, Sch08]. Define f : {−1, 1}n → R>0 as f (x) = 1 − 2ε − I(x). (This is
non-negative valued for ε < 1/24.)
Clearly, deg( f ) = 3 and by the relation between Sherali-Adams relaxations and deg+ , deg+ ( f +
ε) = deg+ (1 − ε − I( )) = Ωε (n). To finish the proof, it remains to show that degε+ ( f ) = O(log(1/ε)).
This follows from a similar argument used in [CLRS13] for MAX-CUT.


Acknowledgements
We thank the Simons Institute for Theory of Computing where part of this work was done as
part of the program on “Fine-grained Complexity” in Fall 2015. We thank Mika Göös, James Lee,
David Steurer, Thomas Vidick for valuable comments. We thank Ryan O’Donnell and Yu Zhao for
pointing out bugs in a previous version of this paper.

29

References
[BFPS15]

Gábor Braun, Samuel Fiorini, Sebastian Pokutta, and David Steurer, Approximation limits
of linear programs (beyond hierarchies), Math. Oper. Res. 40 (2015), no. 3, 756–772.

[BGMT12] Siavosh Bennabas, Konstantinos Georgiou, Avner Magen, and Madhur Tulsiani, SDP
gaps from pairwise independence, Theory of Computing 8 (2012), no. 12, 269–289.
[CG88]

Benny Chor and Oded Goldreich, Unbiased bits from sources of weak randomness and
probabilistic communication complexity, SIAM J. Comput. 17 (1988), no. 2, 230–261.

[CLRS13] Siu On Chan, James R. Lee, Prasad Raghavendra, and David Steurer, Approximate
constraint satisfaction requires large LP relaxations, 54th Annual IEEE Symposium on
Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA,
2013, pp. 350–359.
[CMM09] Moses Charikar, Konstantin Makarychev, and Yury Makarychev, Integrality gaps for
sherali-adams relaxations, Proceedings of the 41st Annual ACM Symposium on Theory of
Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, 2009, pp. 283–292.
[FMP+ 15] Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, and Ronald de Wolf,
Exponential lower bounds for polytopes in combinatorial optimization, J. ACM 62 (2015), no. 2,
17.
[GLM+ 15] Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman,
Rectangles are nonnegative juntas, Proceedings of the Forty-Seventh Annual ACM on
Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015,
2015, pp. 257–266.
[Gri01]

Dima Grigoriev, Complexity of positivstellensatz proofs for the knapsack, Computational
Complexity 10 (2001), no. 2, 139–154.

[LRS15]

James R Lee, Prasad Raghavendra, and David Steurer, Lower bounds on the size of
semidefinite programming relaxations, Proceedings of the forty-seventh annual ACM
symposium on Theory of computing, ACM, 2015.

[LS91]

László Lovász and Alexander Schrijver, Cones of matrices and set-functions and 0-1
optimization, SIAM Journal on Optimization 1 (1991), no. 2, 166–190.

[Raz03]

A. A. Razborov, On the quantum communication complexity of symmetric predicates, Izv.
Ross. Akad. Nauk Ser. Mat. 67 (2003), no. 1, 159–176.

[RM99]

Ran Raz and Pierre McKenzie, Separation of the monotone NC hierarchy, Combinatorica 19
(1999), no. 3, 403–435.

[SA90]

Hanif D. Sherali and Warren P. Adams, A hierarchy of relaxations between the continuous
and convex hull representations for zero-one programming problems, SIAM J. Discrete Math.
3 (1990), no. 3, 411–430.
30

[Sch08]

Grant Schoenebeck, Linear level lasserre lower bounds for certain k-csps, 49th Annual IEEE
Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008,
Philadelphia, PA, USA, 2008, pp. 593–602.

[She11]

Alexander A. Sherstov, The pattern matrix method, SIAM J. Comput. 40 (2011), no. 6,
1969–2000.

[Yan88]

Mihalis Yannakakis, Expressing combinatorial optimization problems by linear programs
(extended abstract), Proceedings of the 20th Annual ACM Symposium on Theory of
Computing, May 2-4, 1988, Chicago, Illinois, USA, 1988, pp. 223–228.

31

