Communication Lower Bounds via

Critical Block Sensitivity∗

Mika Göös and Toniann Pitassi

Department of Computer Science
University of Toronto

Abstract. We use critical block sensitivity, a new complexity measure introduced by

Huynh and Nordström (STOC 2012), to study the communication complexity of search
problems. To begin, we give a simple new proof of the following central result of Huynh and
Nordström: if S is a search problem with critical block sensitivity b, then every randomised
two-party protocol solving a certain two-party lift of S requires Ω(b) bits of communication.
Besides simplicity, our proof has the advantage of generalising to the multi-party setting.
We combine these results with new critical block sensitivity lower bounds for Tseitin and
Pebbling search problems to obtain the following applications.

• Monotone circuit depth: We exhibit a monotone n-variable function in NP whose

√
monotone circuits require depth Ω(n/ log n); previously, a bound of Ω( n) was known
√
(Raz and Wigderson, JACM 1992). Moreover, we prove a Θ( n) monotone depth
bound for a function in monotone P.

• Proof complexity: We prove new rank lower bounds as well as obtain the first
length–space lower bounds for semi-algebraic proof systems, including Lovász–
Schrijver and Lasserre (SOS) systems. In particular, these results extend and
simplify the works of Beame et al. (SICOMP 2007) and Huynh and Nordström.

∗
A preliminary version of this work appeared in the Proceedings of STOC 2014 [GP14].
1 Introduction
Apart from their intrinsic interest, communication lower bounds for search problems find
applications in two major areas of complexity theory.

1. Circuit complexity: A famous theorem of Karchmer and Wigderson [KW88] states

that for all boolean functions f , the minimum depth of a circuit computing f is equal
to the communication complexity of a certain search problem, called the Karchmer–
Wigderson (KW) game for f . While it still remains a major open problem to prove
general depth lower bounds for explicit boolean functions, KW-games have permitted
progress in monotone circuit complexity: there are monotone depth lower bounds for
graph connectivity [KW88], clique functions [GH92, RW92], perfect matchings [RW92],
and functions in monotone P [RM99]. See also Chapter 7 in Jukna’s book [Juk12].

2. Proof complexity: Impagliazzo et al. [IPU94] (see also [Juk12, §19.3]) introduced an
analogue of KW-games to proof complexity. They showed how small tree-like Cutting
Planes refutations of an unsatisfiable CNF formula F can be converted into efficient
two-party communication protocols for a certain canonical search problem associated
with F . More recently, Beame et al. [BPS07] extended this connection by showing
that suitable lower bounds for multi-party protocols imply degree/rank lower bounds
for many well-studied semi-algebraic proof systems, including Lovász–Schrijver [LS91],
Positivstellensatz [Gri01], Sherali–Adams [SA90], and Lasserre (SOS) [Las01] systems.
In parallel to these developments, Huynh and Nordström [HN12] have also found a new
kind of simulation of space-bounded proofs by communication protocols. They used
this connection to prove length–space lower bounds in proof complexity.

In this work we obtain new randomised lower bounds for search problems in both two-party
and multi-party settings. Our proofs are relatively simple reductions from the set-disjointness
function, the canonical NP-complete problem in communication complexity. These results
allow us to derive, almost for free, new lower bounds in the above two application domains.

1. Monotone depth: We introduce a certain monotone encoding of the CSP satisfiability

problem and prove an Ω(n/ log n) monotone depth lower bound for it, where n is the
number of input variables. Previously, the best bound for an explicit monotone function
√
(perfect matchings) was Ω( n) due to Raz and Wigderson [RW92]. Moreover, we prove
√
a Θ( n) monotone depth bound for a function in monotone P.

2. Rank, length, and space: We obtain new rank lower bounds for a family of semantic
polynomial threshold proof systems called Tcc (k), which includes many of the semi-
algebraic proof systems mentioned above. This extends and simplifies the work of
Beame et al [BPS07]. We also extend the length–space lower bound of Huynh and
Nordström [HN12] to hold for Tcc (k) systems of degree up to k = (log n)1−o(1) . In
particular, this yields the first nontrivial length–space lower bounds for dynamic SOS
proofs of this degree.

We state these results more precisely shortly, once we first formalise our basic communication
complexity setup.

1
1.1 Starting point: Critical block sensitivity
We build on the techniques recently introduced by Huynh and Nordström [HN12]. They
defined a new complexity measure for search problems called critical block sensitivity, which
is a generalisation of the usual notion of block sensitivity for functions (see [BdW02] for
a survey). They used this measure to give a general method of proving lower bounds for
composed search problems in the two-party communication model. These notions will be so
central to our work that we proceed to define them immediately.
A search problem on n variables is a relation S ⊆ {0, 1}n × Q where Q is some set of
possible solutions. On input α ∈ {0, 1}n the search problem is to find a solution q ∈ Q that is
feasible for α, that is, (α, q) ∈ S. We assume that S is such that all inputs have at least one
feasible solution. An input is called critical if it has a unique feasible solution.

Definition 1 (Critical block sensitivity [HN12]). Fix a search problem S ⊆ {0, 1}n × Q. Let
f ⊆ S denote a total function that solves S, i.e., for each input α ∈ {0, 1}n the function
picks out some feasible solution f (α) for α. We denote by bs(f, α) the usual block sensitivity
of f at α. That is, bs(f, α) is the maximal number bs such that there are disjoint blocks
of coordinates B1 , . . . , Bbs ⊆ [n] satisfying f (α) 6= f (αBi ) for all i; here, αBi is the same as
α except the input bits in coordinates Bi are flipped. The critical block sensitivity of S is
defined as
cbs(S) := min max bs(f, α).
f ⊆S critical α

We note immediately that cbs(S) is a lower bound on the deterministic decision tree
complexity of S. Indeed, a deterministic decision tree defines a total function f ⊆ S and
on each critical input α the tree must query at least one variable from each sensitive block
of f at α (see [BdW02, Theorem 9]). It turns out that cbs(S) is also a lower bound on the
randomised decision tree complexity (see Theorem 1 below).

1.2 Composed search problems

In order to study a search problem S ⊆ {0, 1}n × Q in the setting of two-party communication
complexity, we need to specify how the n input variables of S are divided between the two
players, Alice and Bob.
Unfortunately, for many search problems (and functions) there is often no partition of the
variables that would carry the “intrinsic” complexity of S over to communication complexity.
For example, consider computing the AND function on n inputs. The block sensitivity of AND
is n, but this complexity is lost once we move to the two-party setting: only O(1) many bits
need to be communicated between Alice and Bob regardless of the input partition.
For this reason, one usually studies composed (or lifted ) variants S ◦ g n of the original
problem; see Figure 1. In a composed problem, each of the n input bits of S are encoded
using a small two-party function g : X × Y → {0, 1}, sometimes called a gadget. As input to
S ◦ g n Alice gets an x ∈ X n and Bob gets a y ∈ Y n . We think of the pair (x, y) as encoding
the input
α = g n (x, y) = ( g(x1 , y1 ), . . . , g(xn , yn ) )
of the original problem S. The objective is to find a q ∈ Q such that (g n (x, y), q) ∈ S.

2
 S S

α1 α2 α3 α4 α5 ; g g g g g

x1 y1 x2 y2 x3 y3 x4 y4 x5 y5

Figure 1: Composing a search problem S with a two-party gadget g.

1.3 Our communication complexity results

We start by giving a simple new proof of the following central result of Huynh and Nord-
ström [HN12]. (Strictly speaking, the statement of the original theorem [HN12] is slightly
weaker in that it involves an additional “consistency” assumption, which we do not need.)

Theorem 1 (Two-party version). There is a two-party gadget g : X × Y → {0, 1} such

that if S ⊆ {0, 1}n × Q is any search problem, then S ◦ g n has randomised bounded-error
communication complexity Ω(cbs(S)).

Huynh and Nordström proved Theorem 1 for the gadget g = 3IND, where 3IND : [3] ×
{0, 1}3 → {0, 1} is the indexing function that maps (x, y) 7→ yx . Their proof used the
information complexity approach [CSWY01, BYJKS04] and is quite intricate. By contrast,
we prove Theorem 1 by a direct randomised reduction from the set-disjointness function

DISJn (x, y) = (ORn ◦ ANDn )(x, y) = i∈[n] (xi ∧ yi ).

W

In the language of Babai et al. [BFS86] (see also [CP10]) the set-disjointness function is
NP-complete in communication complexity: it is easy to certify that DISJn (x, y) = 1, and
conversely, every two-party function with low nondeterministic complexity reduces efficiently
to DISJn . Our proof of Theorem 1 is inspired by a result of Zhang [Zha09] that essentially
establishes Theorem 1 in case S is a function and cbs(S) is simply the standard block
sensitivity. The key insight in our proof is to choose g to be random-self-reducible (see
Section 2 for definitions). Random-self-reducibility is a notion often studied in cryptography
and classical complexity theory, but less often in communication complexity. Most notably,
random-self-reducibility was used implicitly in [RW92]. The definitions we adopt are similar
to those introduced by Feige et al. [FKN94] in a cryptographic context.
Our proof has also the advantage of generalising naturally to the multi-party setting. This
time we start with the k-party unique-disjointness function UDISJk,n and the proof involves
the construction of k-party random-self-reducible functions gk .

Theorem 2 (Multi-party version). There are k-party gadgets gk : X k → {0, 1} with domain
size log |X | = k o(1) bits per player, such that if S ⊆ {0, 1}n × Q is any search problem, then
S ◦ gkn has randomised bounded-error communication complexity at least that of UDISJk,cbs(S)
(up to constants).

Theorem 2 can be applied to the following multi-player communication models.

3
 − Number-in-hand: The i-th player only sees the i-th part of the input. Here, set-
disjointness has been studied under broadcast communication (e.g., [Gro09]) and under
private channel communication [BEO+ 13].
− Number-on-forehead (NOF): The i-th player sees all parts of the input except the
√
i-th part [CFL83]. The current best randomised lower bound for UDISJk,n is Ω( n/2k k)
by Sherstov [She13]. We rely heavily on Sherstov’s result in our proof complexity
applications.
In the rest of this introduction we discuss the applications—the impatient reader who
wants to see the proofs of Theorems 1 and 2 can immediately skip to Sections 2 and 3.

1.4 CSPs and their canonical search problems

To get the most out of Theorems 1 and 2 for the purposes of applications, we need to find
search problems with high critical block sensitivity but low certificate complexity. Low-degree
constraint satisfaction problems (CSPs) capture exactly the latter goal [LNNW95].
Definition 2 (d-CSPs). A CSP F consists of a set of (boolean) variables vars(F ) and a set of
constraints cons(F ). Each constraint C ∈ cons(F ) is a function that maps a truth assignment
α : vars(F ) → {0, 1} to either 0 or 1. If C(α) = 1, we say that C is satisfied by α, otherwise
C is violated by α. Let vars(C) denote the smallest subset of vars(F ) such that C depends
only on the truth values of the variables in vars(C). We say that F is of degree d, or F is
a d-CSP, if |vars(C)| ≤ d for all C. Note that d-CNF formulas are a special case of d-CSPs,
and conversely, each d-CSP can be written as an equivalent d-CNF with a factor 2d blow-up
in the number of constraints.
An unsatisfiable CSP F has no assignment that satisfies all the constraints. Each such F
comes with an associated canonical search problem S(F ).
Definition 3 (Canonical search problems). Let F be an unsatisfiable CSP. In the search
problem S(F ) we are given an assignment α : vars(F ) → {0, 1} and the goal is to find a
constraint C ∈ cons(F ) that is violated by α.
We give new critical block sensitivity lower bounds for the canonical search problems
associated with Tseitin and Pebbling formulas.

1.5 Sensitivity of Tseitin formulas

Tseitin formulas are well-studied examples of unsatisfiable CSPs that are hard to refute in
many proof systems; for an overview, see Jukna [Juk12, §18.7].
Definition 4 (Tseitin formulas). Let G = (V, E, `) be a connected labelled graph of maximum
degree d where the labelling ` : V → {0, 1} has odd Hamming weight. The Tseitin formula
TseG associated with G is the d-CSP that has the edges e ∈ E as variables and for each node
v ∈ V there is a constraint Cv defined by
X
Cv (α) = 1 ⇐⇒ α(e) ≡ `(v) (mod 2).
e:v∈e

It follows from a simple parity argument that TseG is unsatisfiable (see, e.g., Section 4.1).

4
 Call G κ-routable if there is a set T ⊆ V of size |T | ≥ 2κ such that for any set of κ disjoint
pairs of nodes of T there are κ edge-disjoint paths in G that connect all the pairs. (Note:
κ-routability is usually defined only for T = V , but we relax this condition.) The proof of the
following theorem appears in Section 4.
Theorem 3 (Tseitin sensitivity). If G is κ-routable, then cbs(S(TseG )) = Ω(κ).
Theorem 3 can be applied to the following classes of bounded-degree graphs.
√ √ √
− Grid graphs: If G is a n × n grid graph, then we can take κ = Ω( n) by letting
T ⊆ V be any row (or column) of nodes. This is tight: the deterministic decision tree
√
that solves S(TseG ) using binary search makes O( n) queries.
− Expanders: If G is a sufficiently strong expander (e.g., a Ramanujan graph [LPS88]),
then we can take κ = Ω(n/ log n) as shown by Frieze et al. [FZ00, Fri01].
− Connectors: A κ-connector is a bounded-degree graph with κ inputs I ⊆ V and κ
outputs O ⊆ V such that for any one-to-one correspondence π : I → O there exist κ
edge-disjoint paths that connect i ∈ I to π(i) ∈ O. If we merge I and O in a 2κ-connector
in some one-to-one manner and let T = I = O, we get a κ-routable graph. Conversely,
if G is κ-routable, we can partition the set T as I ∪ O and get a κ-connector.
It is known that simple κ-connectors with κ = Θ(n/ log n) exist and this bound is
the best possible [Pip90]. Thus, the best lower bound provable using Theorem 3 is
Θ(n/ log n).
It is well known that the deterministic decision tree complexity of S(TseG ) is Ω(n) when G
is an expander [Urq87]. However, randomised lower bounds—which Theorem 3 provides—are
more scarce. We are only aware of a single previous result in the direction of Theorem 3,
namely, Lovász et al. [LNNW95, §3.2.1] announce a lower bound of Ω(n1/3 ) for the randomised
decision tree complexity of S(TseG ) when G is an expander. Our Theorem 3 subsumes this.

1.6 Sensitivity of pebbling formulas

Pebble games have been studied extensively as means to understand time and space in
computations; for an overview, see the survey by Nordström [Nor13]. In this work we restrict
our attention to the simple (black) pebble game that is played on a directed acyclic graph G
with a unique sink node t (i.e., having outdegree 0). In this game the goal is to place a pebble
on the sink t using a sequence of pebbling moves. The allowed moves are:
(1) A pebble can be placed on a node if its in-neighbours have pebbles on them. In particular,
we can always pebble a source node (i.e., having indegree 0).
(2) A pebble can be removed from any pebbled node (and reused later in the game).
The (black) pebbling number of G is the minimum number of pebbles that are needed to
pebble the sink node in the pebble game on G.
The pebble game on G comes with an associated pebbling formula.
Definition 5 (Pebbling formulas. See [BSW01] and [Nor13, §2.3]). Let G = (V, E, t) be a
directed acyclic graph of maximum indegree d where t is a unique sink. The pebbling formula
PebG associated with G is the (d + 1)-CSP that has the nodes v ∈ V as variables and the
following constraints:

5
 (1) The variable corresponding to the sink t is false.
(2) For all nodes v with in-neighbours w1 , . . . , wd , we require that if all of w1 , . . . , wd are
true, then v is true. In particular, each source node must be true.

It is not hard to see that PebG is unsatisfiable.

Classical complexity measures for S(PebG ) include the pebbling number of G (a measure
of space) and the deterministic decision tree complexity (a measure of parallel time), which
admits many equivalent characterisations [Cha13]. However, these complexity measures are
fundamentally deterministic and do not seem to immediately translate into randomised lower
bounds, which are needed in our applications. For this reason, Huyhn and Nordström [HN12]
devised an elegant ad hoc proof method for their result that, for a pyramid graph G (see Fig-
ure 6), cbs(S(PebG )) = Ω(n1/4 ). Annoyingly, this falls a little short of both the pebbling
√ √
number Θ( n) of G and the decision tree complexity Θ( n) of S(PebG ). Here we close this
gap by generalising their proof method: we get tight bounds for a different (but related)
graph G. The proof appears in Section 4.

Theorem 4 (Pebbling sensitivity). There are bounded-degree graphs G on n nodes such that
√
− G has pebbling number Θ( n).
√
− S(PebG ) has deterministic decision tree complexity Θ( n).
√
− S(PebG ) has critical block sensitivity Θ( n).

1.7 Applications: Monotone depth

Monotone depth from Tseitin. Let G be an Ω(n/ log n)-routable graph of bounded degree
d = O(1). By Theorem 3 the lifted problem S(TseG ) ◦ g O(n) has two-party communication
complexity Ω(n/ log n). By contrast, its nondeterministic communication complexity is just
log n + O(1), since the players can guess a node v ∈ V (G) and verify that it indeed induces
a parity violation (which involves exchanging the inputs to d = O(1) many copies of g
associated to edges incident to v). It is known that any two-party search problem with
nondeterministic communication complexity C reduces to a monotone KW-game for some
monotone f : {0, 1}N → {0, 1} on N = 2C variables; see Gál [Gál01, Lemma 2.3] for an
exposition. In our case we get a monotone function on N = O(n) variables whose monotone
KW-game complexity—i.e., its monotone depth complexity—is Ω(N/ log N ). Moreover, we
make this general connection a bit more explicit in Section 5 by showing that our function
can be taken to be a monotone variant of the usual CSP satisfiability function.

Corollary 5 (Monotone depth from Tseitin). There is an monotone function in NP on N

input bits whose monotone depth complexity is Ω(N/ log N ).

Monotone depth from pebbling. We also get perhaps the simplest proof yet of a nΩ(1)
monotone depth bound for a function in monotone P. Indeed, we only need to apply a
√
transformation of Raz and McKenzie, described in [RM99, §3], which translates our Ω( n)
communication lower bound for S(PebG ) ◦ g O(n) (coming from Theorems 1 and 4) to a
monotone depth lower bounds for a related “generation” function GENG0 defined relative to a
“lifted” version G0 of G0 . Raz and McKenzie originally studied the case when G is a pyramid
graph, and they lifted S(PebG ) with some poly(n)-size gadget (making the number of input

6
bits of GENG0 a large polynomial in n). However, their techniques work for any graph G and
any gadget g. In our case of constant-size gadgets, we get only constant factor blow-up in
parameters; we refer to [RM99, §3] for the details of deriving the following.
Corollary 6 (Monotone depth from pebbling). There is an explicit√function f on N input
bits such that f admits polynomial
√ size monotone circuits of depth Θ( N ) and any monotone
circuit for f requires depth Θ( N ).
The original bounds of [RM99] went up to Ω(N δ ) for a small constant δ. This was
recently improved by the works [CP12, FPRC13] that prove (among other things) monotone
depth bounds of up to Ω(N 1/6−o(1) ) for GENG type functions. Our Corollary 6 achieves
quantitatively the largest bound (to-date) for a function in monotone P.

1.8 Applications: Proof complexity

Over the last decade or so there have been a large number of results proving lower bounds
on the rank required to refute (or approximately optimise over) systems of constraints
in a wide variety of semi-algebraic (a.k.a. polynomial threshold) proof systems, including
Lovász–Schrijver [LS91], Cutting Planes [Gom58, Chv73], Positivstellensatz [Gri01], Sherali–
Adams [SA90], and Lasserre [Las01] proofs. Highlights of this work include recent linear
rank lower bounds for many constraint optimisation problems [Sch08, Tul09, CMM09, STT07,
GMPT10]. Nearly all of these results rely on delicate constructions of local distributions that
are specific to both the problem and to the proof system.
A communication complexity approach for proving lower bounds for semi-algebraic proofs
was developed by Beame et al. [BPS07]. They studied a semantic proof system called Tcc (k)
whose proofs consist of lines that are computed by a low-cost (i.e., polylog communication)
k-party NOF protocols (see Section 6 for definitions). They prove that if a CNF formula
F has a small tree-like Tcc (k) refutation, then S(F ) has an efficient k-party NOF protocol.
Thus, lower bounds for the tree-size of Tcc (k) proofs follow from NOF lower bounds for S(F ).

Rank lower bounds. Using this relationship we can now prove the following result1 for
Tcc (k) proof systems, where k can be almost logarithmic in the size of the formula. We state
the theorem only for rank, with the understanding that a bound of Ω(R) on rank also implies
a bound of exp(Ω(R)) on tree-size. The proof appears in Section 6.
Theorem 7 (Rank lower bounds). There are explicit CNF formulas F of size s and width
O(log s) such that all Tcc (k) refutations of F require rank at least
(
s1−o(1) , for k = 2,
Rk (s) =
s1/2−o(1) , for 3 ≤ k ≤ (log s)1−o(1) .

Theorem 7 simplifies the proof of a similar theorem from [BPS07], which held only for a
specific family of formulas obtained from non-constant degree graphs, and only for k < log log s.
We note already here that the quadratic gap between R2 (s) and R3 (s) will be an artefact
of us switching from two-party communication to multi-party communication. More specifi-
cally, while the two-party communication complexity of set-disjointness DISJn is Ω(n), the
1
Similar claims were made in [BHP10]. Unfortunately, as pointed out by [HN12], Lemma 3.5 in [BHP10] is
incorrect and this renders many of the theorems in the paper incorrect.

7
 √
corresponding lower bound for three parties is only Ω( n) [She13]. Whether the multi-party
bound can be improved to Ω(n) is an open problem.

Length–space lower bounds. Continuing in similar spirit, [HN12] showed how to prove
length–space lower bounds for Tcc (2) systems from lower bounds on the communication
complexity of S(F ). Using this relationship together with our new multi-party lower bounds,
we can extend this result to Tcc (k) systems of degree k > 2.

Theorem 8 (Length–space lower bounds). There are CNF formulas F of size s such that

− F admits a Resolution refutation of length L = s1+o(1) and space Sp = s1/2+o(1) .

− Any length L and space Sp refutation of F in Tcc (k) must satisfy
(
s1/2−o(1) , for k = 2,
Sp · log L ≥ (1)
s1/4−o(1) , for 3 ≤ k ≤ (log s)1−o(1) .

We hesitate to call Theorem 8 a tradeoff result since our only upper bound is a refutation
requiring space Sp = s1/2+o(1) and we do not know how to decrease this space usage by
trading it for length; this is the same situation as in [HN12]. Surprisingly, in a subsequent
work, Galesi et al. [GPT15] have shown that any unsatisfiable CNF formula admits an
exponentially long Cutting Planes refutation in constant space, which gives a second data
point in the length–space parameter space for which an upper bound exists. We also mention
that while the CNF formulas F in Theorem 8 are lifted versions of pebbling formulas, we
could have formulated similar length–space lower bounds for lifted Tseitin formulas (where,
e.g., Sp · log L ≥ s1−o(1) for k = 2). But for Tseitin formulas we do not have close-to-matching
upper bounds.
In any case, Theorem 8 gives, in particular, the first length–space lower bounds for dynamic
SOS proofs of degree k. In addition, even in the special case of k = 2, Theorem 8 simplifies
and improves on [HN12]. However, for Polynomial Calculus Resolution (a Tcc (2) system), the
best known length–space tradeoff results are currently proved in the recent work of Beck et
al. [BNT13]. For Resolution (maybe the simplest Tcc (2) system), even stronger tradeoff results
have been known since [BSN11]; see also Beame et al. [BBI12] for nontrivial length lower
bounds in the superlinear space regime. For Cutting Planes (a Tcc (2) system) Theorem 8
remains the state-of-the-art to our knowledge.

1.9 Models of communication complexity

We work in the standard models of two-party and multi-party communication complexity;
see [KN97, Juk12] for definitions. Here we only recall some conventions about randomised
protocols. A protocol Π solves a search problem S with error  iff on any input x the
probability that (x, Π(x)) ∈ S is at least 1 −  over the random coins of the protocol. Note
that Π(x) need not be the same feasible solution; it can depend on the outcomes of the
random coins. The protocol is of bounded-error if  ≤ 1/4. The constant 1/4 here can often be
replaced with any other constant less than 1/2 without affecting the definitions too much. In
the case of computing boolean functions this follows from standard boosting techniques [KN97,
Exercise 3.4]. While these boosting techniques may fail for general search problems, we do
not encounter any such problems in this work.

8
2 Versatile Gadgets
In this section we introduce versatile two-party and multi-party functions. Our proofs of
Theorems 1 and 2 will work whenever we choose g or gk to be a versatile gadget. We start by
introducing the terminology in the two-party case; the multi-party case will be analogous.

2.1 Self-reductions and versatility

The simplest reductions between communication problems are those that can be computed
without communication. Let fi : Xi × Yi → {0, 1} for i = 1, 2, be two-party functions. We
say that f1 reduces to f2 , written f1 ≤ f2 , if the communication matrix of f1 appears as a
submatrix of the communication matrix of f2 . Equivalently, f1 ≤ f2 iff there exist one-to-one
mappings πA and πB such that

f1 (x, y) = f2 (πA (x), πB (y)) for all (x, y) ∈ X1 × Y1 .

Our restriction to one-to-one reductions above is merely a technical convenience (cf. Babai et
al. [BFS86] allow reductions to be many-to-one).
Example 1. Let 3EQ : [3] × [3] → {0, 1} be the equality function with inputs from [3]. Then
AND reduces to 3EQ since AND(x, y) = 3EQ(1 + x, 3 − y).
We will be interested in special kinds of reductions that reduce a function to itself. Our
first flavour of self-reducibility relates a function f and its negation ¬f :

Flippability. A function f is called flippable if ¬f ≤ f . Note that since the associated

reduction maps z-inputs to (1 − z)-inputs in a one-to-one fashion, a flippable function
must be balanced : exactly half of the inputs satisfy f (x, y) = 1.

Example 2. The XOR function is flippable via ¬XOR(x, y) = XOR(1 − x, y). By contrast,
AND and 3EQ are not balanced and hence not flippable.
We will also consider randomised reductions where the two parties are allowed to synchro-
nise their computations using public randomness. More precisely, even though the two parties
are still not communicating, we can let the mappings πA and πB depend on a public random
string r ∈ {0, 1}∗ , whose distribution the two parties can freely choose. This way, a random
reduction computes (x, y) 7→ (πA (x, r), πB (y, r)). The following definition is similar to the
perfectly secure functions of Feige et al. [FKN94].

Random self-reducibility. A function f is called random-self-reducible if there are

mappings πA and πB together with a random variable r such that for every z-input
(x, y) ∈ f −1 (z) the random pair (πA (x, r), πB (y, r)) is uniformly distributed among
all the z-inputs of f .

Example 3. The equality function EQ : [n] × [n] → {0, 1} is random-self-reducible: we can use
the public randomness to sample a permutation π : [n] → [n] uniformly at random and let the
two parties compute (x, y) 7→ (π(x), π(y)). (In fact, to further save on the number of random
bits used, it would suffice to choose π from any group that acts 2-transitively on [n].)

9
 0 1 2 3
0 0 0 1 1
1 0 1 1 0 1 0 0 0 1 1
2 1 1 0 0 0 1 0 1 0 1
3 1 0 0 1 0 0 1 1 1 0

Figure 2: Function VER. Figure 3: Function HN.

A notable example of a function that is not random-self-reducible is AND; it has only

one 1-input, which forces any self-reduction to be the identity map. This is particularly
inconvenient since AND is featured in the set-disjointness function DISJn = ORn ◦ ANDn ,
which will be the starting point for our reductions. To compensate for the shortcomings of
AND we work with a slightly larger function g ≥ AND instead.

Definition 6 (Versatility). A two-party function g is called versatile if (1) g ≥ AND, (2) g is

flippable, and (3) g is random-self-reducible.

2.2 Two-party example

Consider the function VER : Z4 × Z4 → {0, 1} defined by

VER(x, y) = 1 ⇐⇒ x + y ∈ {2, 3}, for all x, y ∈ Z4 , (2)

where the arithmetic is that of Z4 ; see Figure 2.

Lemma 9. VER is versatile.

Proof. The reduction from AND is simply given by AND(x, y) = VER(x, y). Moreover, VER
is flippable because ¬VER(x, y) = VER(x + 2, y). To see that VER is random-self-reducible,
start with (x, y) and compute as follows. First, choose (x, y) uniformly at random from the
set {(x, y), (1 − x, −y)} so that x + y is uniformly distributed either in the set {0, 1} if (x, y)
was a 0-input, or in the set {2, 3} if (x, y) was a 1-input. Finally, choose a random a ∈ Z4
and output (x + a, y − a).

It is not hard to show that VER is in fact a minimum-size example of a versatile function:
if g : [a] × [b] → {0, 1} is versatile then a, b ≥ 4. Indeed, VER is the smallest two-party
function for which our proof of Theorem 1 applies. By comparison, the original proof of
Theorem 1 [HN12] uses a certain subfunction HN ≤ 3IND whose communication matrix
is illustrated in Figure 3. Thus, somewhat interestingly, our proof yields a result that is
incomparable to [HN12] since we have neither VER ≤ HN nor HN ≤ VER.
Coincidentally, VER makes an appearance in Sherstov’s pattern matrix method [She11,
§12], too. There, the focus is on exploiting the matrix-analytic properties of the communication
matrix of VER. By contrast, in this work, we celebrate its self-reducibility properties.

10
2.3 Multi-party examples
In the multi-party setting we restrict our attention to k-party reductions f1 ≤ f2 for k-party
functions fi : Xik → {0, 1} that are determined by one-to-one mappings π1 , . . . , πk satisfying

f1 (x1 , . . . , xk ) = f2 (π1 (x1 ), . . . , πk (xk )) for all (x1 , . . . , xk ) ∈ X1k .

This way any player that sees an input xi can evaluate πi (xi ) without communication. As
before, a randomised reduction can also depend on public coins.
Versatile k-party functions gk : X k → {0, 1} are defined analogously to the two-party case:
we require that the k-party k-bit ANDk function reduces to gk , and that gk is both flippable
and random-self-reducible—all under k-party reductions.
It is known that every k-party function is a subfunction of some, perhaps exponentially
large random-self-reducible function [FKN94]. However, in the following, we are interested in
finding examples of small versatile k-party functions in order to optimise our constructions.
We proceed to give two examples of well-studied k-party functions and prove them versatile.

First example: Quadratic character. Denote by χ : Z× p → {0, 1} the indicator function

for quadratic residuosity modulo p, i.e., χ(x) = 1 iff x is a square in Zp . The pseudo-random
qualities of χ have often made it an object of study in communication complexity [BNS92,
BGKL03, ACFN12]. Moreover, the self-reducibility properties of χ are famously useful in
cryptography, starting with [GM84].
For our purposes we let p to be an O(k)-bit prime. Following [BNS92, §2.5] the k-party
quadratic character function QCSk : Zkp → {0, 1} is defined as
P

QCSk (x1 , . . . , xk ) := χ i xi . (3)
P
We leave QCSk (x1 , . . . , xk ) undefined for inputs with i xi = 0, i.e., we consider QCSk to be
a promise problem. Our three items of versatility fall out of the well-known properties of χ.
Lemma 10. QCSk is versatile.
Proof. Reduction from ANDk : We need the following nonelementary fact (see, e.g., Lemma 6.13
in [BGKL03] or the recent work [Wri13]): if p is a large enough O(k)-bit prime then there are
k + 1 consecutive integers {a, a + 1, . . . , a + k} ⊆ Z×
k realising the pattern

χ(a) = χ(a + 1) = · · · = χ(a + k − 1) = 0 and χ(a + k) = 1.

This immediately facilitates the reduction: an input (y1 , . . . , yk ) of ANDk is mapped to an

input (a + y1 , y2 , . . . , yk ) of QCSk . Flippability: Map xi 7→ s · xi for all i, where s 6= 0 is a
fixed quadratic nonresidue. Random-self-reducibility: Choose a random quadratic residue
r ∈ Zp and numbers a1 , . . . , ak ∈ Zp satisfying a1 + · · · + ak = 0. The random self-reduction
maps xi 7→ r · xi + ai for all i.

Second example: Pointer jumping. Next, we observe that certain variants of the k-party
pointer jumping function are versatile. To explain this idea, we begin by describing a simple
construction where each of the k inputs requires Θ(k log k) bits to represent. After this we
improve on the construction by using known results on branching programs; we note that
similar ideas have been used in the context of secure multi-party computations [CFIK03].

11
 — layer 1
Figure 4: Example of AND3 ≤ Jump3 . x1 :
The input (x1 , x2 , x3 ) of Jump3 is the — layer 2
result of applying the reduction to the x2 :
— layer 3
input (1, 0, 1) of AND3 .
x3 :
— layer 4
0 0 0 1 1 1 (labelled)

Define the k-party pointer jumping function Jumpk : X k → {0, 1} as follows. The inputs
are permutations xi : [2k] → [2k], i ∈ [k], and the function value is given by

Jumpk (x1 , . . . , xk ) = 0 ⇐⇒ (xk ◦ xk−1 ◦ · · · ◦ x1 )(1) ∈ [k]. (4)

A useful way to view the input (x1 , . . . , xk ) is as a layered digraph: there are k + 1 layers, each
containing 2k nodes; the input xi defines a perfect matching between layers i and i + 1; and
the nodes on the last layer are labelled in a balanced way with k zeroes and k ones. The value
of the function is the label of the sink that is reachable from the 1st node of the 1st layer.

Lemma 11. Jumpk is versatile.

Proof. Reduction from ANDk : Given an input (y1 , . . . , yk ) of ANDk we reduce it to an input
(x1 , . . . , xk ) of Jumpk as follows (see Figure 4). If yi = 0 then xi is defined to be the
identity permutation on [2k], otherwise xi is the cyclic permutation that maps j 7→ j + 1 for
j ∈ [2k − 1] and 2k 7→ 1. Flippability: Replace the input xk with π ◦ xk , where π : [2k] → [2k]
is some fixed permutation that swaps the sets [k] and [k + 1, 2k], i.e., π([k]) = [k + 1, 2k].
Random-self-reducibility: The random self-reduction is best visualised as acting on the
layered graph associated with an input (x1 , . . . , xk ). First, sample k + 1 permutations
π1 , . . . , πk+1 : [2k] → [2k] uniformly and independently at random under the restrictions that
π1 fixes the element 1 and πk+1 fixes the set [k]. Then use πi to relabel the nodes on the i-th
layer. Formally this means that the input xi is mapped to πi+1 ◦ xi ◦ πi−1 .

The reduction ANDk ≤ Jumpk above was implicitly using a simple read-once permutation
branching program for ANDk ; see Figure 4. We will now optimise this construction by using
more efficient branching programs.

Definition 7 (PBPs). A permutation branching program (PBP) of width w and length ` is

defined by a sequence of instructions (il , πl , τl ), l ∈ [`], where πl , τl : [w] → [w] are permutations
and each il ∈ [n] indexes one of the n input variables x1 , . . . , xn . Let an input x ∈ {0, 1}n be
given. We say that an instruction (i, π, τ ) evaluates to π if xi = 0; otherwise the instruction
evaluates to τ . The PBP evaluates to the composition of the permutations evaluated at the
instructions. Finally, if γ : [w] → [w] is a permutation, we say that the PBP γ-computes a
function f : {0, 1}n → {0, 1} if it evaluates to the identity permutation e : [w] → [w] on each
0-input in f −1 (0) and to the permutation γ 6= e on each 1-input in f −1 (1).

Lemma 12. Suppose there exists a width-w length-` PBP that γ-computes the ANDk function.
Then there exists a versatile k-party function on O(`w log w) input bits.

12
Proof. Fix a width-w PBP (il , πl , τl ), l ∈ [`], that γ-computes ANDk . By modifying the PBP
if necessary, we may assume that w is even and γ(1) ∈ [w/2 + 1, w]. The versatile function
corresponding to the given PBP is the pointer jumping function Jump`k (x1 , . . . , x` ) defined
similarly to (4):

Jump`k (x1 , . . . , x` ) = 0 ⇐⇒ (x` ◦ x`−1 ◦ · · · ◦ x1 )(1) ∈ [w/2].

To define the input partition, let Li := {l ∈ [`] : il = i} be the set of layers where the PBP
reads the i-th input. We let the i-th player hold (on its forehead) the inputs xl for l ∈ Li .
Reduction from ANDk : The reduction ANDk ≤ Jump`k is naturally determined by the PBP:
given an input (y1 , . . . , yk ) of ANDk , we define xl to be the permutation that the instruction
(il , πl , τl ) evaluates to under (y1 , . . . , yk ). Because of our input partition, it is possible to
compute xl without communication.
Flippability and random-self-reducibility: Same as in the proof of Lemma 11.

Barrington’s celebrated theorem [Bar89] gives a PBP implementation of ANDk with

parameters w = 5 and ` = O(k 2 ). This corresponds to having O(k) input bits per player,
matching the quadratic character example above. Cleve [Cle91] has improved this to a tradeoff
result where for any  > 0 one can take ` = k 1+ provided that w = w() is a large enough
constant. Cleve’s construction also has the property that every input variable of ANDk is
read equally many times (i.e., the Li in the above proof have the same size). Thus, letting
w grow sufficiently slowly, we get a versatile k-party gadget on O(`w log w) = k 1+o(1) bits,
which is k o(1) bits per player.

Corollary 13. There are versatile k-party gadgets gk : X k → {0, 1} where log |X | = k o(1) .

3 Communication Lower Bound

In this section we prove the communication lower bound for two parties (Theorem 1) assuming
that g is a versatile gadget. The generalisation to multiple parties (Theorem 2) follows by the
same argument—one only needs to replace g with a versatile k-party gadget gk .
Our proof builds on a result of Zhang [Zha09] that lower bounds the two-party communi-
cation complexity of a composed function f ◦ g n in terms of the block sensitivity of f . We
start by outlining Zhang’s approach.

3.1 Functions: Zhang’s approach

Zhang [Zha09] proved the following theorem by a reduction from the unique-disjointness
function UDISJn . Here, UDISJn = ORn ◦ ANDn is the usual set-disjointness function together
with the promise that if UDISJn (a, b) = 1, then there is a unique coordinate i ∈ [n] such
that ai = bi = 1. The randomised communication complexity of UDISJn is well-known to be
Θ(n) [KS92, Raz92, BYJKS04]. Zhang’s proof works for any gadget g with AND, OR ≤ g.

Theorem 14 (Zhang). There is a two-party gadget g : X ×Y → {0, 1} such that if f : {0, 1}n →
Q is a function, then f ◦ g n has communication complexity Ω(bs(f )).

13
 The proof runs roughly as follows. Fix an input α ∈ {0, 1}n for f that witnesses the block
sensitivity bs(f, α) = bs(f ). Also, let B1 , . . . , Bbs ⊆ [n] be the sensitive blocks of f at α.
Given an input (a, b) to UDISJbs the goal in the reduction is for the two parties to compute,
without communication, an input (x, y) for f ◦ g n such that
(T1) 0-inputs: If UDISJbs (a, b) = 0, then g n (x, y) = α.
(T2) 1-inputs: If UDISJbs (a, b) = 1 with ai = bi = 1, then g n (x, y) = αBi .
Clearly, if we had a reduction (a, b) 7→ (x, y) satisfying (T1–T2), then the output of
UDISJbs (a, b) could be recovered from (f ◦ g n )(x, y). Thus, an -error protocol for f ◦ g n would
imply an -error protocol for UDISJbs with the same communication cost.

3.2 Search problems: Our approach

We are going to prove Theorem 1 (restated below) in close analogy to the proof template
(T1–T2) above. However, as discussed below, noncritical inputs to search problems introduce
new technical difficulties.
Theorem 1 (Two-party version). There is a two-party gadget g : X × Y → {0, 1} such
that if S ⊆ {0, 1}n × Q is any search problem, then S ◦ g n has randomised bounded-error
communication complexity Ω(cbs(S)).

Setup. Fix any versatile gadget g : X × Y → {0, 1}. Let Π be a randomised -error protocol
for a composed search problem S ◦ g n . Recall that an input (x, y) for the problem S ◦ g n is
critical if there is exactly one solution q with ((x, y), q) ∈ S ◦ g n . In particular, if g n (x, y) is
critical for S, then (x, y) is critical for S ◦ g n . The behaviour of the protocol Π on a critical
input (x, y) is predictable: the protocol’s output Π(x, y) is the unique solution with probability
at least 1 − .
However, noncritical inputs (x, y) are much trickier: not only can the distribution of the
output Π(x, y) be complex, but the distributions of Π(x, y) and Π(x0 , y 0 ) can differ even if
(x, y) and (x0 , y 0 ) encode the same input g n (x, y) = g n (x0 , y 0 ) of S. The latter difficulty is the
main technical challenge, and we address it by using random-self-reducible gadgets.

Defining a function f ⊆ S. We start by following very closely the initial analysis in the
proof of Huynh and Nordström [HN12]. First, we record for each α ∈ {0, 1}n the most likely
feasible output of Π on inputs (x, y) that encode α. More formally, for each α we define µα to
be the uniform distribution on the set of preimages of α, i.e.,
µα is uniform on {(x, y) : g n (x, y) = α}. (5)
Alternatively, this can be viewed as a product distribution
µ α = µ α1 × µ α2 × · · · × µ αn , (6)
where µz , z ∈ {0, 1}, is the uniform distribution on g −1 (z).
The most likely feasible solution output by Π on inputs (x, y) ∼ µα is now captured by a
total function f ⊆ S defined by
f (α) := arg max Pr [ Π(x, y) = q ]. (7)
q:(α,q)∈S (x,y)∼µα

14
Here, ties are broken arbitrarily and the randomness is taken over both (x, y) ∼ µα and the
random coins of the protocol Π. (Note that, in general, the most likely output of Π(x, y) may
not be feasible. However, above, we explicitly pick out the most likely feasible solution. Thus,
f is indeed a subfunction of S.)

The sensitive critical input. We can now use the critical block sensitivity of S: there is
a critical input α such that bs(f, α) ≥ cbs(S). Let B1 , . . . , Bbs ⊆ [n] be the sensitive blocks
with f (αBi ) 6= f (α).
Lemma 15. The protocol Π can distinguish between µα and µαBi in the sense that
(x, y) ∼ µα =⇒ Pr[ Π(x, y) = f (α) ] ≥ 1 − , (8)
(x, y) ∼ µαBi =⇒ Pr[ Π(x, y) = f (α) ] ≤ 1/2. (9)
Proof. The consequent in the first property (8) is true even for each individual (x, y) in the
support of µα since α is critical. To see that the second property (9) is true, suppose for a
contradiction that we had Pr[ Π(x, y) = f (α) ] > 1/2 for (x, y) ∼ µαBi . By averaging, there
is a fixed input (x, y) in the support of µαBi such that Pr[ Π(x, y) = f (α) ] > 1/2. By the
correctness of Π (i.e., 1 −  > 1/2) this implies that f (α) is feasible for αBi . Thus, f (α) is the
most likely feasible solution output by Π(x, y), that is, f (αBi ) = f (α) by the definition (7).
But this contradicts the fact that f is sensitive to Bi at α.

The reduction. Lemma 15 suggests a reduction strategy analogous to the template (T1–T2)
of Section 3.1. Given an input (a, b) for UDISJbs our goal is to describe a randomised reduction
(a, b) 7→ (x, y) such that
(P1) 0-inputs: If UDISJbs (a, b) = 0, then (x, y) ∼ µα .
(P2) 1-inputs: If UDISJbs (a, b) = 1 with ai = bi = 1, then (x, y) ∼ µαBi .
Suppose for a moment that we had a reduction with properties (P1–P2). Let Π0 be the
protocol that on input (a, b) first applies the reduction (a, b) 7→ (x, y) with properties (P1–P2),
then runs Π on (x, y), and finally outputs 0 if Π(x, y) = f (α) and 1 otherwise. Lemma 15
tells us that
− If UDISJbs (a, b) = 0, then Π0 (a, b) = 0 with probability at least 1 − .
− If UDISJbs (a, b) = 1, then Π0 (a, b) = 1 with probability at least 1/2.
The error probability of Π0 can be bounded away from 1/2 by repeating Π0 twice and
outputting 0 iff both runs of Π0 output 0. (Here we are assuming that  is small enough, say
at most 1/4. If not, we can use some other standard success probability boosting tricks.) This
gives a randomised protocol for UDISJbs with the same communication cost (up to constants)
as that of Π. Theorem 1 follows.
Indeed, it remains to implement a reduction (a, b) 7→ (x, y) satisfying (P1–P2). We do it
in three steps; see Figure 5.

Step 1. On input (a, b) = (a1 . . . abs , b1 . . . bbs ) to UDISJbs we first take each pair (ai , bi )
through the reduction AND ≤ g to obtain instances (a01 , b01 ), . . . , (a0bs , b0bs ) of g. Note that
− if UDISJbs (a, b) = 0, then g(a0i , b0i ) = 0 for all i;
− if UDISJbs (a, b) = 1, then there is a unique i with g(a0i , b0i ) = 1.

15
 S

g g g g g g g

—– Step 3

(1, 1) (0, 0) —– Step 2

AND ≤g AND ≤g —– Step 1

(a1 , b1 ) (a2 , b2 )

Figure 5: The reduction (a, b) 7→ (x, y). In this example bs = 2 and n = 7. The
critical input is α = 1011010 and the two sensitive blocks are B1 = {2, 3, 4} and
B2 = {6, 7}. The input pair (ai , bi ), i = 1, 2, is plugged in for the block Bi .

Step 2. Next, the instances (a0i , b0i ) are used to populate a vector (x, y) = (x1 . . . xn , y1 . . . yn )
carrying n instances of g, as follows. The instance (a0i , b0i ) is plugged in for the coordinates
j ∈ Bi with the copies corresponding to αj = 1 flipped. That is, we define for j ∈ Bi :

− if αj = 0, then (xj , yj ) := (a0i , b0i );

− if αj = 1, then (xj , yj ) := (πA (a0i ), πB (b0i )), where (πA , πB ) is the reduction ¬g ≤ g.

/ ∪i Bi we simply fix an arbitrary (xj , yj ) ∈ g −1 (αj ). We now have that

For j ∈

− if UDISJbs (a, b) = 0, then g n (x, y) = α;

− if UDISJbs (a, b) = 1 with ai = bi = 1, then g n (x, y) = αBi .

Step 3. Finally, we apply a random-self-reduction independently for each component (xi , yi )

of (x, y): this maps a z-input (xi , yi ) to a uniformly random z-input (xi , yi ) ∼ µz . The result
is a random vector (x, y) that has a distribution of the form (6) and matches our requirements
(P1–P2), as desired.

This concludes the proof of Theorem 1. The proof of the multi-party version (Theorem 2)
is exactly the same, except with g and UDISJbs replaced by a versatile gk and UDISJk,bs .
Here, in particular, UDISJk,n is the usual k-party disjointness function DISJk,n = ORn ◦ ANDnk
together with the promise that at most one of the ANDk ’s evaluates to 1.

16
4 Critical Block Sensitivity Lower Bounds
In this section we prove our new critical block sensitivity bounds, Theorems 3 and 4.

4.1 Tseitin sensitivity

Let G = (V, E, `) be a connected graph with an odd-weight labelling ` : V → {0, 1}. Recall
that in the problem S(TseG ) the input is an assignment α : E → {0, 1} and the goal is to find
a parity violation, that is, a node in Viol(α) := {v ∈ V : Cv (α) = 0}.
For the readers’ convenience, we recall some P basic
P facts about TseG . Since each edge
e ∈ EPparticipates in two constraints, the sum v e:v∈e α(e) will be even. By contrast, the
sum v `(v) is odd. It follows that |Viol(α)| must be odd, and, in particular, non-empty.
Conversely, for every odd-size set U ⊆ V , there is an α with Viol(α) = U . To see this, start
with any assignment E → {0, 1} and let p be a simple path in G. If we flip the truth values
of the edges in p, we end up flipping whether or not the constraints at the endpoints of p are
satisfied. Depending on whether the endpoints of p were satisfied to begin with, this results
in one of the following scenarios: (1) we create a pair of violations; (2) we remove a pair of
violations; or (3) we move a violation from one endpoint of p to the other. It is not hard to
see that by using (1)–(3) repeatedly, we can design an assignment α such that Viol(α) = U .
We are now ready to prove Theorem 3.

Theorem 3 (Tseitin sensitivity). If G is κ-routable, then cbs(S(TseG )) = Ω(κ).

Proof. Let G = (V, E, `) be (κ + 1)-routable. Fix a set T ⊆ V of size |T | = 2κ + 1 such

that whenever M is a set of κ disjoint pairs of nodes from T , there are κ edge-disjoint paths
connecting each pair in M . We denote by Paths(M ) some canonical set of such paths.
Consider the following bipartite auxiliary graph on left and right vertices:

− Left vertices are pairs (α, M ), where α : E → {0, 1} has a unique violation that is in
T (i.e., |Viol(α)| = 1 and Viol(α) ⊆ T ), and M is a partition of the set T r Viol(α) into
κ pairs of nodes.

− Right vertices are pairs (α0 , M 0 ), where α0 : E → {0, 1} has three violations that are all
in T (i.e., |Viol(α0 )| = 3 and Viol(α0 ) ⊆ T ), and M 0 is a partition of the set T r Viol(α0 )
into κ − 1 pairs of nodes.

− Edges are defined as follows. A left vertex (α, M ) is connected to a right vertex (α0 , M 0 )
if M 0 ⊆ M and α0 is obtained from α by flipping the values along the path in Paths(M )
that connects the pair Viol(α0 ) r Viol(α).

The key fact, which is easy to verify, is that the auxiliary graph is biregular : its left-degree is
κ and its right-degree is 3.
To prove the block sensitivity bound, let f be a function solving S(TseG ). We say that
an edge from (α, M ) to (α0 , M 0 ) in the auxiliary graph is sensitive if f (α) 6= f (α0 ). Clearly,
for each right vertex exactly two (out of three) of its incident edges are sensitive. Thus, by
averaging, we may find a left vertex (α, M ) such that at least a fraction 2/3 of its incident
edges are sensitive. But this means that α is a critical input with block sensitivity at least 2κ/3;
the blocks are given by a subset of Paths(M ).

17
 t t

⊆ = ×

Figure 6: Pyramid graph viewed as a subgraph of a tensor product of paths.

4.2 Pebbling sensitivity

Theorem 4 (Pebbling sensitivity). There are bounded-degree graphs G on n nodes such that
√
− G has pebbling number Θ( n).
√
− S(PebG ) has deterministic decision tree complexity Θ( n).
√
− S(PebG ) has critical block sensitivity Θ( n).

Overview. Our proof of Theorem 4 generalises the original proof from [HN12] that held
for pyramid graphs. The key idea is natural: In a pyramid graph, each horizontal layer can
be interpreted as a path—this is made precise by viewing the pyramid graph as a subgraph of
a tensor product of paths as in Figure 6. The analysis in the original proof suffered from the
fact that random walks do not mix well on paths. So, we replace the paths by graphs with
better mixing properties! (Perhaps surprisingly, we do not need to rely on expanders here.)

Definition of G. Let H be the 3-dimensional grid graph on m = r3 nodes where r is odd.

For convenience, we think of H as a directed Cayley graph on Z3r generated by the 6 elements

B = {±(1, 0, 0), ±(0, 1, 0), ±(0, 0, 1)}.

That is, there is an edge (v, u) ∈ E(H) iff u = v + b for some b ∈ B. The key property of H
(which is not satisfied by d-dimensional grid graphs for d < 3) is the following.

Lemma 16 (Partial cover time). Starting from any node of H the expected number of steps
it takes for a random walk to visit at least half of the nodes of H is pct(H) = O(m).

Proof. This follows from Lemma 2.8 in [Lov93] and the fact that the maximum hitting time
of H is O(m) (e.g., [CRR+ 96]).

Let ` := 2 · pct(H) + 1 = Θ(m) so that by Markov’s inequality a random walk of length

` − 1 in H will cover a at least a fraction 1/2 of H with probability at least 1/2. Let P be the
directed path on [`] with edges (i, i + 1), i ∈ [` − 1]. We construct the tensor product graph

G := H × P

that is defined by V (G) = Z3r × [`] and there is a directed edge from (v, i) to (u, j) iff j = i + 1
and u = v + b for some b ∈ B.
The n = m` nodes of G are naturally partitioned into ` layers (or steps). In order to
turn G into a pebbling formula, we need to fix some sink node t in the `-th layer and delete
all nodes from which t is not reachable. We do not let this clean-up operation affect our

18
notations, though. For example, we continue to think of the resulting graph as G = H × P .
The nodes Z3r × {1} of indegree 0 will be the sources.
Note that each source–sink path p in G contains exactly one node from each layer. We
view the projection of p onto H as a walk of length ` − 1 in H; we can describe the walk
uniquely by a sequence of ` − 1 generators from B. We denote by π(p) ⊆ V (H) the set of
nodes visited by the projected walk.
We can now study the search problem S(PebG ) associated with the pebbling formula PebG .
√
Pebbling number. The pebbling strategy for G that uses O( n) = O(m) pebbles proceeds
as follows. We first pebble the 1st layer (the sources), then the 2nd layer, then remove pebbles
from the 1st layer, then pebble the 3rd layer, then remove pebbles from the 2nd layer, etc.
The matching lower bound follows from the fact that G contains a pyramid graph on Ω(n)
√
nodes as a subgraph, and the pebbling number of pyramid graphs is Θ( n) [Coo74].
√
Decision tree complexity. The deterministic decision tree that uses O( n) = O(m)
queries proceeds as follows. We start our search for a violated clause at the sink t. If the sink
variable is false, we query its children to find a child v whose associated variable is false. The
search continues at v in the same manner. In at most ` − 1 = O(m) steps we find a false node
v whose children are all true (perhaps v is a source node).
The matching lower bound follows from the critical block sensitivity lower bound proved
below, and the fact that critical block sensitivity is a lower bound on the decision tree
complexity.

Critical block sensitivity. It remains to prove that cbs(S(PebG )) = Ω(m). The following
proof is a straightforward generalisation of the original proof from (the full version of) [HN12].
All paths that we consider in the following are source–sink paths in G. We associate with
each path p a critical input αp : V (G) → {0, 1} that assigns to each node on p the value 0 and
elsewhere the value 1. This creates a unique clause violation at the source where p starts.
If p and q are two paths, we say that p and q are paired at i ≥ 2 if the following hold.
− Agreement: p and q do not meet before layer i, but they agree on all layers i, . . . , `.
− Mirroring: if the first i − 1 steps of p are described by (b1 , b2 , . . . , bi−1 ) ∈ B i−1 , then the
first i − 1 steps of q are described by (−b1 , −b2 , . . . , −bi−1 ) ∈ B i−1 .
Each path can be paired with at most ` − 1 other paths—often, there are plenty such:
Lemma 17. Each path p is paired with at least |π(p)| − 1 other paths.
Proof. For each node v ∈ π(p), except the starting point of p, we construct a pair q for p. To
this end, let i ≥ 2 be the first step at which the projection of p visits v. Since the mirroring
property uniquely determines q given p and i, we only need to show that this q satisfies the
agreement property. Thus, suppose for a contradiction that p and q meet at some node (u, j)
where j < i. We have, in Z3r arithmetic,

v = u + bj + bj+1 + · · · + bi−1 (according to p),

v = u − bj − bj+1 − · · · − bi−1 (according to q).

This implies 2v = 2u, but since r is odd, we get v = u. This contradicts our choice of i.

19
 If p and q are paired, we can consider the assignment αp∪q that is the node-wise logical
AND of the assignments αp and αq . In αp∪q we have two clause violations associated with the
two starting points of the paths.
To prove the critical block sensitivity bound Ω(m), let f be a function solving S(PebG ).
Consider the following auxiliary graph.
− The vertices are the source–sink paths.
− There is a directed edge from p to q iff p and q are paired and f (αp∪q ) is the starting
point of q. Thus, each two paired paths are connected by an edge one way or the other.
Recall that if we start a random walk of length ` − 1 on H at any fixed node, the walk covers
a fraction ≥ 1/2 of H with probability ≥ 1/2. If we view a source-sink path p in G in the
reverse order (starting at the sink and going towards the source), this translates into saying
that |π(p)| ≥ m/2 for a fraction ≥ 1/2 of all paths p. Applying Lemma 17 for such paths we
conclude that the auxiliary graph has average outdegree at least d = m/8 − 1. By averaging,
we can now find a path p with out-neighbours q1 , . . . , qd . Define qi0 := qi r p. Clearly the
critical assignment αp is sensitive to each qi0 . To see that the qi0 are pairwise disjoint, we note
that they take steps in the same direction in B at each layer (i.e., opposite to that of p), and
the qi meet p for the first time at distinct layers. This concludes the proof of Theorem 4.

5 Monotone CSP-SAT
In this section we introduce a monotone variant of the CSP satisfiability problem and show
how lifted search problems S(F ) ◦ g n reduce to its monotone Karchmer–Wigderson game. In
particular, in Corollary 5 we can take the explicit function to be a CSP satisfiability function.
We also note that our function has been further studied by Oliveira [Oli15, Chapter 3].

Definition of monotone CSP-SAT. The function is defined relative to some finite alpha-
bet Σ and a fixed constraint topology given by a bipartite graph G with left vertices V (variable
nodes) and right vertices U (constraint nodes). We think of each v ∈ V as a variable taking on
values from Σ; an edge (v, u) ∈ E(G) indicates that variable v is involved in constraint node u.
Let d be the maximum degree of a node in U . We define SAT = SATG,Σ : {0, 1}N → {0, 1} on
N ≤ |U | · |Σ|d bits as follows. An input α ∈ {0, 1}N describes a CSP instance by specifying,
for each constraint node u ∈ U , its truth table: a list of at most |Σ|d bits that record which
assignments to the variables involved in u satisfy u. Then SAT(α) := 1 iff the CSP instance
described by α is satisfiable. This encoding of CSP satisfiability is indeed monotone: if we
flip any 0 in a truth table of a constraint into a 1, we are only making the constraint easier to
satisfy.

5.1 Reduction to CSP-SAT

Recall the characterisation of monotone depth due to Karchmer and Wigderson [KW88]: if
f : {0, 1}N → {0, 1} is a monotone function, then its monotone depth complexity is equal to
the (deterministic) communication complexity of the following search problem.
Monotone KW-game for f : Alice holds a a ∈ f −1 (1) and Bob holds a b ∈
f −1 (0). The goal is to find a coordinate i ∈ [N ] such that ai = 1 and bi = 0.

20
The next lemma shows that for any search problem of the form S(F ) ◦ g n there is a some
monotone CSP-SAT function whose monotone KW-game embeds S(F ) ◦ g n . (The reduction
can be seen as a generalisation of Lemma 3.5 in [RM99].)
We define the constraint topology of F naturally as the bipartite graph G with left vertices
vars(F ) and right vertices cons(F ). For a constraint C ∈ cons(F ) we use the lower case c to
denote the corresponding node in G (forgetting that C is actually a function).

Lemma 18. Let g : X × Y → {0, 1} be a two-party gadget and let F be an unsatisfiable

d-CSP on n variables and m constraints. Let G be the constraint topology of F . Then the
monotone depth complexity of SATG,X : {0, 1}N → {0, 1}, N ≤ m|X |d , is lower bounded by
the (deterministic) communication complexity of S(F ) ◦ g n .

Proof. We reduce the search problem S(F ) ◦ g n to the monotone KW-game for SATG,X . To
this end, let (x, y) be an input to the search problem S(F ) ◦ g n and compute as follows.

− Alice maps x ∈ X vars(F ) to the CSP whose sole satisfying assignment is x. That is,
the truth table for a constraint node c is set to all-0 except for the entry indexed by
x  vars(C) (restriction of x to the variables in C).

− Bob maps y ∈ Y vars(F ) to an unsatisfiable CSP as follows. The truth table for a
constraint node c is such that the bit indexed by ` ∈ X vars(C) is set to 1 iff C is satisfied
under the partial assignment v 7→ g(`(v), y(v)) where v ∈ vars(C).

Alice clearly constructs a 1-input of SATG,X . To see that Bob constructs a 0-input
of SATG,X , suppose for a contradiction that there is a global assignment ` : vars(F ) → X
so that the truth table of each c has a 1 in position indexed by `  vars(C). This would
mean that the truth assignment v 7→ g(`(v), y(v)) satisfies all the constraints of F . But this
contradicts the unsatisfiability of F .
Assume then that Alice and Bob run a protocol for the monotone KW-game on the CSP
instances constructed above. The output of the protocol is a some entry ` ∈ X vars(C) in the
truth table of some constraint node c where Alice has a 1 and Bob has a 0. Because Alice’s
CSP was constructed so that for each constraint node c exactly one entry is 1, we must have
that ` = x  vars(C). On the other hand, Bob’s construction ensures that C is not satisfied
under the assignment v 7→ g(`(v), y(v)) = g(x(v), y(v)). Thus, we have found a violated
constraint C for the canonical search problem for F .

5.2 Proof of Corollary 5

Theorems 1 and 3 yield a search problem S(TseG )◦g m of communication complexity Ω(n/ log n)
where G is an n-node m-edge bound-degree graph (d = O(1), m = O(n)) and g is a constant-
size gadget (|X | = O(1)). Using Lemma 18 we can then construct a CSP-SAT function on
N = O(n) bits having monotone depth Ω(n/ log n) = Ω(N/ log N ). This proves Corollary 5.

6 Applications: Proof Complexity

In this section we prove our new proof complexity lower bounds as stated in Section 1.8. We
start by reviewing some standard proof complexity terminology.

21
6.1 Background
In this work we focus on proof systems that refute unsatisfiable CNF formulas. Given a
proof system, a refutation (or a proof ) P of an unsatisfiable CNF formula F in the system is
expressed as a sequence of lines, denoted Lines(P ), each of which is either (a translation of) a
clause of F or follows from some previous lines via some sound inference rule. The refutation
ends with some trivially false line.
For each proof P we can associate a directed acyclic graph GP = (V, E) where V = Lines(P )
and there is an edge (u, v) ∈ E if v is derived via some inference rule using line u.

Complexity measures. For the purposes of this work, we define the size of a proof P
simply as the number of lines |Lines(P )|. The rank of P is the length of the longest path in
GP . The size complexity and rank complexity of F in a proof system are the minimum size
and minimum rank, respectively, of all refutations of F in that system.
We consider GP to be a tree if every internal node has fan-out one, that is, the clauses of
F , which are not internal nodes, can be repeated. If GP is a tree, we say that P is tree-like.
The tree-like size complexity of F is the minimum size of a tree-like refutation of F . Note
that restricting a refutation to be tree-like does not increase the rank because each line can
be re-derived multiple times without affecting the rank. Tree-like size, however, can be much
larger than general size.

Examples of proof systems. We mention some of the most well-studied proof systems.
In each of these systems, there is a set of derivation rules (which can be thought of as
inference schemas) of the form F1 , F2 , . . . , Ft ` Ft+1 and each inference in a proof must be an
instantiation of one of these rules.
A basic system is Resolution whose lines are clauses. Its only rule is the resolution rule:
the clause (A ∨ B) can be derived from (A ∨ x) and (B ∨ ¬x), where A and B are arbitrary
disjunctions of literals and x is a variable. A Resolution refutation of an unsatisfiable CNF
formula f is a sequence of clauses, ending with the empty clause, such that each clause in
the sequence is either a clause of f , or follows from two previously derived clauses via the
resolution rule.
Another proof system is the Cutting Planes (CP) proof system that manipulates integer
linear inequalities. A CP refutation is a sequence of inequalities, ending with 0 ≥ 1, such
that all inequalities are either translations of clauses of F , or follow from two previously
derived inequalities via one of the two CP rules, addition and division with rounding. There
is a natural extension of CP, denoted CP(k), in which the above CP proof rules may also be
applied when the lines are allowed to be degree k multivariate polynomials.
Other important well-studied proof systems are the Lovász–Schrijver proof systems (LS0 ,
LS, LS+ , and LS+,? ) which are dynamic proof systems that manipulate polynomial inequalities
of degree at most 2; the Sherali–Adams and Lasserre (SOS) systems that are static proof
systems allowing polynomial inequalities of higher degree; and the dynamic Lasserre (dynamic
SOS), and LSk+,? systems, which generalize the Lovász–Schrijver systems to higher degree. We
refer the reader to [OZ13] for formal definitions and a thorough history for these and related
proof sytems.

22
Semantic proof systems. Each of the above proof systems has a specific set of inference
rule schemas, which allows them to have polynomial-time verifiers. In this work we consider
more powerful semantic proof systems that restrict the form of the lines and the fan-in of
the inferences but dispense with the requirement of a polynomial-time verifier and allow any
semantically sound inference rule with a given fan-in. The fan-in must be restricted because
the semantic rules are so strong. The following system was introduced in [BPS07].

Definition 8 (Degree k threshold proofs). We denote by Th(k) the semantic proof system
whose proofs have fan-in 2 and each line in a refutation of a formula F is a polynomial
inequality of degree at most k in the variables of F . In particular, each clause of F enters the
system as translated into a linear inequality (similarly to the CP system discussed above).

The following lemma follows from Caratheodory’s Theorem.

Lemma 19. CP and LS proofs can be efficiently converted into Th(k) proofs:

• Any CP proof of size (tree-like size) s and rank r can be converted to a Th(1) proof of
size (tree-like size) O(s) and rank O(r log s).

• Any LS0 , LS, or LS+ proof of size (tree-like size) s and rank r can be converted to a
Th(2) proof of size (tree-like size) O(s) and rank O(r log s).

Moreover, it is not hard to show that one can extend the above simulations by Th(k)
proofs to CP(k), LSk+,? , and degree k (dynamic) Lasserre proofs.
In this paper we consider semantic proof systems that are even more general than Th(k),
namely those for which the fan-in is bounded and the truth value of each line can be computed
by an efficient multi-party NOF communication protocol.

Definition 9 (Proofs with k-party verifiers). We denote by Tcc (k, c) the semantic proof
system of fan-in 2 in which each proof line is a boolean function whose value, for every k-
partition of the input variables, can be computed by a c-bit randomised k-party NOF protocol
of error at most 1/4. Both k = k(s) and c = c(s) may be functions of s, the size of the input
formula. In keeping with the usual notions of what constitutes efficient communication, we
use Tcc (k) to denote Tcc (k, polylog s).

Note that via standard boosting, we can replace the error 1/4 in the above definition by 
at the cost of increasing c by an O(log 1/) factor. Therefore, without loss of generality, in
the definition of Tcc (k) we can assume that the error is at most 2− polylog s .
For polylogarithmic k, the following lemma shows that Th(k) is a subclass of Tcc (k + 1).

Lemma 20. Every Th(k) refutation of an n-variable CNF formula is a Tcc (k +1, O(k 3 log2 n))
refutation.

Proof. By the well-known result of Muroga [Mur71], linear threshold functions on n boolean
variables only require coefficients of O(n log n) bits. Since a degree k threshold polynomial is
a linear function on at most nk monomials, it is equivalent to a degree k threshold polynomial
with coefficients of O(knk log n) bits. As shown in [BPS07], over any input partition there is
a randomized (k + 1)-party communication protocol of cost O(k log2 b) and error ≤ 1/bΩ(1) to
verify a degree k polynomial inequality with b-bit coefficients.

23
 The following lemma, which is implicit in [BPS07], gives the key relationships between
Tcc (k) and randomised communication protocols for S(F ).

Lemma 21. If a CNF formula F has a Tcc (k, c) refutation of rank r then, over any k-partition
of the variables, there is a randomised bounded-error k-party NOF protocol for S(F ) with
communication cost O(c · r log r).

6.2 Lifting CNF formulas

In order to import our communication lower bounds to proof complexity, we need to encode
composed search problems S ◦ gkn as CNF formulas. We describe a natural way of doing this
in case S = S(F ) is the search problem associated with some CNF formula F .
Fix a d-CNF formula F on n variables and m clauses. Also, fix a k-party gadget gk : X k →
{0, 1} where each player holds l := log |X | bits as input. We construct a new D-CNF formula
F ◦ gkn on N variables and M clauses, where

D = d · kl, N = n · kl, and M ≤ m · 2dkl . (10)

Variables of F ◦ gkn . For each variable x of F we create a matrix of variables

X = { Xij : i ∈ [k], j ∈ [l] }.

The idea is that truth assignments αX : X → {0, 1} are in a natural one-to-one correspondence
with the set X k , the domain of gk . Namely, the value of the j-th bit of the i-th player is
encoded by Xij . We take the variable set of F ◦ gkn to be the union X ∪ Y ∪ . . ., where x, y, . . .
are the original variables of F .

Clauses of F ◦ gkn . Let C be a clause of F ; suppose first that C = (x ∨ ¬y) for simplicity.
We will replace C with a set of clauses C on the variables X ∪ Y such that all clauses of C are
satisfied under an assignment α : X ∪ Y → {0, 1} if and only if gk (αX ) = 1 or gk (αY ) = 0;
here αX and αY are elements of X k associated with the restrictions of α to X and Y . Indeed,
let Xijα = Xij if α(Xij ) = 1, and Xijα = ¬Xij if α(Xij ) = 0, and similarly for Yijα . Define a
clause  ^   ^ 
Cα = ¬ Xijα ∨ ¬ Yijα ,
i,j i,j

and let C consist of all the clauses Cα where α is such that gk (αX ) = 0 and gk (αY ) = 1.
More generally, if we had started with a clause on d variables, each clause Cα would involve
dkl variables and so we would have |C| ≤ 2dkl . This completes the description of F ◦ gkn .

The formula F ◦ gkn comes with a natural partition of the variables into k parts as determined
by the k-party gadget. Thus, we can consider the canonical search problem S(F ◦ gkn ).

Lemma 22. The two problems S(F ◦ gkn ) and S(F ) ◦ gkn have the same k-party communication
complexity up to an additive dkl term.

24
Proof. As discussed above, the inputs to the two problems are in a natural one-to-one
correspondence. How about translating solutions between the problems? Given a violated
clause Cα in the problem S(F ◦gkn ), it is easy to reconstruct C from Cα without communication.
Moreover, given a violated clause C of F in the problem S(F ) ◦ gkn , we can construct a violated
Cα by first finding out what encoding α was used for each of the d variables of C. This can
be done by communicating dkl bits (even in the number-in-hand model).

6.3 Rank lower bounds

We are now ready to prove Theorem 7, restated here for convenience.
Theorem 7 (Rank lower bounds). There are explicit CNF formulas F of size s and width
O(log s) such that all Tcc (k) refutations of F require rank at least
(
s1−o(1) , for k = 2,
Rk (s) =
s1/2−o(1) , for 3 ≤ k ≤ (log s)1−o(1) .

Proof. We start with a Tseitin formula F with n variables, O(n) clauses, and width O(1) that
is associated with a Ω(n/ log n)-routable bounded-degree graph. Let k = k(n) be a parameter.
We construct the formula F ◦ gkn where gkn : X k → {0, 1} is the gadget of Corollary 13. Recall
that log |X | = k  where  = (k) → 0 as k → ∞. Using (10), we observe
− F ◦ gkn has size s = O(n) · exp(O(k 1+ )),
− F ◦ gkn has width O(k 1+ ), p
− S(F ◦ gkn ) has k-party NOF communication complexity CC = Ω( n/ log n/2k k); this
follows from Lemma 22, Theorems 2 and 3, and Sherstov’s lower bound [She13]. (Alter-
natively, the complexity is Ω(n/ log n) in case k = 2.)
Fix δ > 0 and choose k = (log n)1−δ . For large n, the above bounds translate into:

s = n1+o(1) , width ≤ log n, and CC ≥ n1/2−o(1) .

Therefore, by Lemma 21, there are no Tcc (k) refutations of F ◦ gkn with rank at most
n1/2−o(1) / polylog n = n1/2−o(1) . The result follows by letting δ → 0 sufficiently slowly.

6.4 Length–space lower bounds

In order to study the space that is required by a refutation, we need to switch to a more
appropriate space-oriented view of proofs.
Definition 10 (Space-oriented proofs. E.g., [Nor13, §2.2]). A refutation of a CNF formula F
in length L and space Sp is a sequence of configurations D0 , . . . , DL where each Di is a set of
lines (of the underlying proof system) satisfying |Di | ≤ Sp and such that D0 = ∅, DL contains
a trivially false line, and Di is obtained from Di−1 via one of the following derivation steps:
− Clause download: Di = Di−1 ∪ {vC } where vC is a translation of some clause C of F .
− Inference: Di = Di−1 ∪ {v} where v follows from some number of lines of Di−1 by an
inference rule of the system.
− Erasure: Di = Di−1 r {v} for some v ∈ Di−1 .

25
 Huynh and Nordström [HN12] proved that if F has a Tcc (2) refutation of short length
and small space, then there is a low-cost randomised two-party protocol for S(F ). It is
straightforward to show that this result holds more generally for Tcc (k) proofs and k-party
protocols. The high level idea is that the players can use the refutation of F to do a binary
search for a violated clause.
Lemma 23 (Simulation of space-bounded proofs). Fix a CNF formula F of size s and some
k-partition of its variables. If F has a Tcc (k) refutation of length L and space Sp, then there
is a k-party randomised bounded-error protocol for S(F ) of communication cost
Sp · log L · polylog s.
Proof. Let α : vars(F ) → {0, 1} be an input to the search problem S(F ). Fix a length-L
space-Sp refutation of F with configurations D0 , . . . , DL .
We will describe a k-party protocol to find a clause of F that is violated under α. The
k players first consider the configuration DL/2 in the refutation and communicate in order
to evaluate the truth value of all lines in DL/2 under α. If all lines of DL/2 are true, they
continue their search on the subderivation DL/2 , . . . , DL , and otherwise the search continues
on the subderivation D0 , . . . , DL/2 . In this way, we do a binary search, always maintaining
the invariant that the first configuration in the subderivation evaluates to true, but some line
in the last configuration evaluates to false. After log L steps, the players will find an i ∈ [L]
such that all of Di−1 evaluates to true but some line in Di is false under α. By the soundness
of the proof system, the false line in Di must have been a download of a some clause of F and
this clause solves the search problem.
Let us analyse the communication complexity of the protocol. The cost of evaluating any
particular configuration with error at most (4 log L)−1 ≤ (4s)−1 is Sp · polylog s. Thus the
overall cost is Sp · log L · polylog s and the total error is at most 1/4.

Huynh and Nordström proceeded to construct formulas PebG of size s such that they
admit Resolution refutations of size O(s), but for which any Tcc (2) refutation in space Sp
and length L must satisfy Sp · log L = s1/4−o(1) . Using our multi-party lower bounds, we can
now generalise this tradeoff result to Tcc (k) proof systems. Namely, we prove the following
result, which was stated in the introduction.
Theorem 8 (Length–space lower bounds). There are CNF formulas F of size s such that
− F admits a Resolution refutation of length L = s1+o(1) and space Sp = s1/2+o(1) .
− Any length L and space Sp refutation of F in Tcc (k) must satisfy
(
s1/2−o(1) , for k = 2,
Sp · log L ≥ (1)
s1/4−o(1) , for 3 ≤ k ≤ (log s)1−o(1) .
Proof. The formula family, parameterised by n ∈ N, is
PebG ◦ gkn ,
where G is the graph from Theorem 4 with n nodes and maximum degree d = O(1), and where
k = k(n) is a parameter, and where gk : X k → {0, 1} is again our gadget from Corollary 13.
In particular, letting l = log |X |, these formulas have size
s ≤ Θ(n) · 2dkl .

26
Lower bound. Using cbs(S(PebG )) = Ω(n1/2 ) and an argument similar to the proof of
Theorem 7, we conclude that S(PebG ◦ gkn ) has k-party randomised communication complexity
Ω(n1/4−o(1) ) when we choose k = (log n)1−o(1) appropriately. (Alternatively, the complexity
is Ω(n1/2−o(1) ) for k = 2.) Recall also that with this choice of k, we have s = n1+o(1) . This
proves the lower bound (1) in view of Lemma 23.

Upper bound (sketch). To see that the lifted formula PebG ◦gkn has a Resolution refutation
of length s1+o(1) and space s1/2+o(1) , we will mimic the usual length-O(n) space-O(n1/2 )
refutation of the original formula PebG . This refutation follows the pebbling of G: whenever
a node v, with in-neighbours w1 , . . . , wd , is pebbled, we derive the clause (v) from previously
derived clauses (w1 ), . . . , (wd ) and the clause (¬w1 ∨ · · · ∨ ¬wd ∨ v) of PebG .
For the lifted version PebG ◦ gkn we want to do the same thing, deriving the lifted clauses
associated with (v) from the lifted clauses associated with (w1 ), . . . , (wd ) and (¬w1 ∨ · · · ∨
¬wd ∨ v). The number of lifted variables that underlie each pebbling step is dkl, and since
there is always a Resolution refutation of size exponential in the number of variables, it follows
that each resolution step in the original refutation of PebG can be simulated by O(2dkl ) = so(1)
steps in the lifted proof. Thus the total length of the lifted refutation is O(n) · so(1) = s1+o(1) .
Similarly, the space used is s1/2+o(1) .

Acknowledgements
We thank Yuval Filmus for pointing out the quadratic character example, and Jakob Nordström
and Thomas Watson for providing helpful suggestions based on an early draft of this work.
Thanks to Nathan Grosshans for e-mail correspondence, which clarified our presentation of
the monotone CSP-SAT function. We also thank Anil Ada, Paul Beame, Trinh Huynh, and
Robert Robere for discussions, and finally the STOC reviewers for useful comments.
This research was supported in part by NSERC. The first author also acknowledges support
from Alfred B. Lehman Graduate Scholarship.

References
[ACFN12] Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, and Phuong Nguyen. The NOF
multiparty communication complexity of composed functions. In Proceedings of
the 39th International Colloquium on Automata, Languages, and Programming
(ICALP), volume 7391 of Lecture Notes in Computer Science, pages 13–24.
Springer, 2012. doi:10.1007/978-3-642-31594-7 2.

[Bar89] David A. Mix Barrington. Bounded-width polynomial-size branching programs

recognize exactly those languages in NC1 . Journal of Computer and System
Sciences, 38(1):150–164, 1989. doi:10.1016/0022-0000(89)90037-8.

[BBI12] Paul Beame, Christopher Beck, and Russell Impagliazzo. Time-space tradeoffs in
resolution: Superpolynomial lower bounds for superlinear space. In Proceedings
of the 44th Symposium on Theory of Computing (STOC), pages 213–232, New
York, NY, USA, 2012. ACM. doi:10.1145/2213977.2213999.

27
[BdW02] Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree
complexity: a survey. Theoretical Computer Science, 288(1):21–43, 2002. doi:
10.1016/S0304-3975(01)00144-X.

[BEO+ 13] Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, and Vinod
Vaikuntanathan. A tight bound for set disjointness in the message-passing model.
In Proceedings of the 54th Symposium on Foundations of Computer Science
(FOCS), pages 668–677. ACM, 2013. doi:10.1109/FOCS.2013.77.

[BFS86] László Babai, Péter Frankl, and János Simon. Complexity classes in communica-
tion complexity theory. In Proceedings of the 27th Symposium on Foundations of
Computer Science (FOCS), pages 337–347. IEEE, 1986. doi:10.1109/SFCS.1986.15.

[BGKL03] László Babai, Anna Gál, Peter G. Kimmel, and Satyanarayana V. Lokam. Com-
munication complexity of simultaneous messages. SIAM Journal on Computing,
33(1):137–166, 2003. doi:10.1137/S0097539700375944.

[BHP10] Paul Beame, Trinh Huynh, and Toniann Pitassi. Hardness amplification in proof
complexity. In Proceedings of the 42nd Symposium on Theory of Computing
(STOC), pages 87–96. ACM, 2010. doi:10.1145/1806689.1806703.

[BNS92] László Babai, Noam Nisan, and Márió Szegedy. Multiparty protocols, pseudo-
random generators for logspace, and time–space trade-offs. Journal of Computer
and System Sciences, 45(2):204–232, 1992. doi:10.1016/0022-0000(92)90047-M.

[BNT13] Chris Beck, Jakob Nordström, and Bangsheng Tang. Some trade-off results for
polynomial calculus (extended abstract). In Proceedings of the 45th Symposium
on Theory of Computing (STOC), pages 813–822. ACM, 2013. doi:10.1145/2488608.
2488711.

[BPS07] Paul Beame, Toniann Pitassi, and Nathan Segerlind. Lower bounds for Lovász–
Schrijver systems and beyond follow from multiparty communication complexity.
SIAM Journal on Computing, 37(3):845–869, 2007. doi:10.1137/060654645.

[BSN11] Eli Ben-Sasson and Jakob Nordström. Understanding space in proof complexity:
Separations and trade-offs via substitutions (extended abstract). In Proceedings
of the 2nd Symposium on Innovations in Computer Science (ICS), pages 401–416.
Tsinghua University Press, 2011.

[BSW01] Eli Ben-Sasson and Avi Wigderson. Short proofs are narrow—resolution made
simple. Journal of the ACM, 48(2):149–169, 2001. doi:10.1145/375827.375835.

[BYJKS04] Ziv Bar-Yossef, T.S. Jayram, Ravi Kumar, and D. Sivakumar. An information
statistics approach to data stream and communication complexity. Journal of
Computer and System Sciences, 68(4):702–732, 2004. doi:10.1016/[Link].2003.11.006.

[CFIK03] Ronald Cramer, Serge Fehr, Yuval Ishai, and Eyal Kushilevitz. Efficient multi-
party computation over rings. In Proceedings of the 22nd International Conference
on the Theory and Applications of Cryptographic Techniques (EUROCRYPT),

28
 volume 2656 of Lecture Notes in Computer Science, pages 596–613. Springer,
2003. doi:10.1007/3-540-39200-9 37.

[CFL83] Ashok K. Chandra, Merrick L. Furst, and Richard J. Lipton. Multi-party protocols.
In Proceedings of the 15th Symposium on Theory of Computing (STOC), pages
94–99. ACM, 1983. doi:10.1145/800061.808737.

[Cha13] Siu Man Chan. Just a pebble game. In Proceedings of the 28th Conference on
Computational Complexity (CCC), pages 133–143, 2013. doi:10.1109/CCC.2013.22.

[Chv73] Vašek Chvátal. Edmonds polytopes and a hierarchy of combinatorial problems.

Discrete Mathematics, 4(4):305–337, 1973. doi:10.1016/0012-365X(73)90167-2.

[Cle91] Richard Cleve. Towards optimal simulations of formulas by bounded-width

programs. Computational Complexity, 1(1):91–105, 1991. doi:10.1007/BF01200059.

[CMM09] Moses Charikar, Konstantin Makarychev, and Yury Makarychev. Integrality gaps
for Sherali–Adams relaxations. In Proceedings of the 41st Symposium on Theory
of Computing (STOC), pages 283–292. ACM, 2009. doi:10.1145/1536414.1536455.

[Coo74] Stephen A. Cook. An observation on time-storage trade off. Journal of Computer

and System Sciences, 9(3):308–316, 1974. doi:10.1016/S0022-0000(74)80046-2.

[CP10] Arkadev Chattopadhyay and Toniann Pitassi. The story of set disjointness.
SIGACT News, 41(3):59–85, 2010. doi:10.1145/1855118.1855133.

[CP12] Siu Man Chan and Aaron Potechin. Tight bounds for monotone switching
networks via Fourier analysis. In Proceedings of the 44th Symposium on Theory
of Computing (STOC), pages 495–504. ACM, 2012. doi:10.1145/2213977.2214024.

[CRR+ 96] Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo, Roman Smolensky,
and Prasoon Tiwari. The electrical resistance of a graph captures its commute and
cover times. Computational Complexity, 6(4):312–340, 1996. doi:10.1007/BF01270385.

[CSWY01] Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, and Andrew C.-C. Yao. In-
formational complexity and the direct sum problem for simultaneous message
complexity. In Proceedings of the 42nd Symposium on Foundations of Computer
Science (FOCS), pages 270–278. IEEE, 2001. doi:10.1109/SFCS.2001.959901.

[FKN94] Uri Feige, Joe Killian, and Moni Naor. A minimal model for secure computation.
In Proceedings of the 26th Symposium on Theory of Computing (STOC), pages
554–563. ACM, 1994. doi:10.1145/195058.195408.

[FPRC13] Yuval Filmus, Toniann Pitassi, Robert Robere, and Stephen A. Cook. Average
case lower bounds for monotone switching networks. In Proceedings of the 54th
Symposium on Foundations of Computer Science (FOCS), pages 598–607. ACM,
2013. doi:10.1109/FOCS.2013.70.

[Fri01] Alan Frieze. Edge-disjoint paths in expander graphs. SIAM Journal on Computing,
30(6):1790–1801, 2001. doi:10.1137/S0097539700366103.

29
[FZ00] Alan Frieze and Lei Zhao. Optimal construction of edge-disjoint paths in random
regular graphs. Combinatorics, Probability and Computing, 9:241–263, 4 2000.
doi:10.1017/S0963548300004284.

[Gál01] Anna Gál. A characterization of span program size and improved lower bounds
for monotone span programs. Computational Complexity, 10(4):277–296, 2001.
doi:10.1007/s000370100001.

[GH92] Mikael Goldmann and Johan Håstad. A simple lower bound for monotone clique
using a communication game. Information Processing Letters, 41(4):221–226,
1992. doi:10.1016/0020-0190(92)90184-W.

[GM84] Shafi Goldwasser and Silvio Micali. Probabilistic encryption. Journal of Computer
and System Sciences, 28(2):270–299, 1984. doi:10.1016/0022-0000(84)90070-9.

[GMPT10] Konstantinos Georgiou, Avner Magen, Toniann Pitassi, and Iannis Tourlakis.
Integrality gaps of 2−o(1) for vertex cover SDPs in the Lovász–Schrijver hierarchy.
SIAM Journal on Computing, 39(8):3553–3570, 2010. doi:10.1137/080721479.

[Gom58] Ralph E. Gomory. Outline of an algorithm for integer solutions to linear programs.
Bulletin of the American Mathematical Society, 64:275–278, 1958.

[GP14] Mika Göös and Toniann Pitassi. Communication lower bounds via critical block
sensitivity. In Proceedings of the 46th Symposium on Theory of Computing
(STOC), pages 847–856. ACM, 2014. doi:10.1145/2591796.2591838.

[GPT15] Nicola Galesi, Pavel Pudlák, and Neil Thapen. The space complexity of cutting
planes refutations. In Proceedings of the 30th Conference on Computational
Complexity (CCC), pages 433–447. Schloss Dagstuhl, 2015. doi:10.4230/[Link].
2015.433.

[Gri01] Dima Grigoriev. Linear lower bound on degrees of Positivstellensatz calculus

proofs for the parity. Theoretical Computer Science, 259(1–2):613–622, 2001.
doi:10.1016/S0304-3975(00)00157-2.

[Gro09] André Gronemeier. Asymptotically optimal lower bounds on the NIH-multi-party

information complexity of the AND-function and disjointness. In Proceedings of
the 26th International Symposium on Theoretical Aspects of Computer Science
(STACS), pages 505–516, 2009. doi:10.4230/[Link].2009.1846.

[HN12] Trinh Huynh and Jakob Nordström. On the virtue of succinct proofs: amplifying
communication complexity hardness to time–space trade-offs in proof complexity.
In Proceedings of the 44th Symposium on Theory of Computing (STOC), pages
233–248. ACM, 2012. doi:10.1145/2213977.2214000.

[IPU94] Russell Impagliazzo, Toniann Pitassi, and Alasdair Urquhart. Upper and lower
bounds for tree-like cutting planes proofs. In Proceedings of the 9th Symposium
on Logic in Computer Science (LICS), pages 220–228. IEEE, 1994. doi:10.1109/
LICS.1994.316069.

30
[Juk12] Stasys Jukna. Boolean Function Complexity: Advances and Frontiers, volume 27
of Algorithms and Combinatorics. Springer, 2012.

[KN97] Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge

University Press, 1997.

[KS92] Bala Kalyanasundaram and Georg Schnitger. The probabilistic communication

complexity of set intersection. SIAM Journal on Discrete Mathematics, 5(4):545–
557, 1992. doi:10.1137/0405044.

[KW88] Mauricio Karchmer and Avi Wigderson. Monotone circuits for connectivity
require super-logarithmic depth. In Proceedings of the 20th Symposium on Theory
of Computing (STOC), pages 539–550. ACM, 1988. doi:10.1145/62212.62265.

[Las01] Jean B. Lasserre. An explicit SDP relaxation for nonlinear 0-1 programs. In
Proceedings of the 8th International Conference on Integer Programming and
Combinatorial Optimization (IPCO), volume 2081 of Lecture Notes in Computer
Science, pages 293–303. Springer, 2001. doi:10.1007/3-540-45535-3 23.

[LNNW95] László Lovász, Moni Naor, Ilan Newman, and Avi Wigderson. Search problems
in the decision tree model. SIAM Journal on Discrete Mathematics, 8(1):119–132,
1995. doi:10.1137/S0895480192233867.

[Lov93] László Lovász. Random walks on graphs: A survey. Combinatorics, Paul Erdős
is eighty, 2:1–46, 1993.

[LPS88] Alexander Lubotzky, Ralph Phillips, and Peter Sarnak. Ramanujan graphs.
Combinatorica, 8(3):261–277, 1988. doi:10.1007/BF02126799.

[LS91] László Lovász and Alexander Schrijver. Cones of matrices and set-functions
and 0–1 optimization. SIAM Journal on Optimization, 1(2):166–190, 1991.
doi:10.1137/0801013.

[Mur71] Saburo Muroga. Threshold logic and its applications. John Wiley & Sons, 1971.

[Nor13] Jakob Nordström. Pebble games, proof complexity, and time-space trade-offs.
Logical Methods in Computer Science, 9(3:15):1–63, 2013. doi:10.2168/LMCS-9(3:
15)2013.

[Oli15] Igor Oliveira. Unconditional Lower Bounds in Complexity Theory. PhD thesis,
Columbia University, 2015. doi:10.7916/D8ZP45KT.

[OZ13] Ryan O’Donnell and Yuan Zhou. Approximability and proof complexity. In
Proceedings of the 24th Symposium on Discrete Algorithms (SODA), pages 1537–
1556. SIAM, 2013.

[Pip90] Nicholas Pippenger. Communication networks. In Jan van Leeuwen, editor,

Handbook of Theoretical Computer Science, volume A, chapter 15, pages 805–833.
Elsevier, 1990.

31
[Raz92] Alexander A. Razborov. On the distributional complexity of disjointness. Theo-
retical Computer Science, 106(2):385–390, 1992. doi:10.1016/0304-3975(92)90260-M.

[RM99] Ran Raz and Pierre McKenzie. Separation of the monotone NC hierarchy.
Combinatorica, 19(3):403–435, 1999. doi:10.1007/s004930050062.

[RW92] Ran Raz and Avi Wigderson. Monotone circuits for matching require linear depth.
Journal of the ACM, 39(3):736–744, 1992. doi:10.1145/146637.146684.

[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 Journal on Discrete Mathematics, 3(3):411–430, 1990. doi:10.1137/0403036.

[Sch08] Grant Schoenebeck. Linear level Lasserre lower bounds for certain k-CSPs. In
Proceedings of the 49th Symposium on Foundations of Computer Science (FOCS),
pages 593–602. IEEE, 2008. doi:10.1109/FOCS.2008.74.

[She11] Alexander A. Sherstov. The pattern matrix method. SIAM Journal on Computing,
40(6):1969–2000, 2011. doi:10.1137/080733644.

[She13] Alexander A. Sherstov. Communication lower bounds using directional derivatives.

In Proceedings of the 45th Symposium on Theory of Computing (STOC), pages
921–930. ACM, 2013. doi:10.1145/2488608.2488725.

[STT07] Grant Schoenebeck, Luca Trevisan, and Madhur Tulsiani. A linear round lower
bound for Lovász–Schrijver SDP relaxations of vertex cover. In Proceedings of
the 22nd Conference on Computational Complexity (CCC), pages 205–216. IEEE,
2007. doi:10.1109/CCC.2007.2.

[Tul09] Madhur Tulsiani. CSP gaps and reductions in the Lasserre hierarchy. In Pro-
ceedings of the 41st Symposium on Theory of Computing (STOC), pages 303–312.
ACM, 2009. doi:10.1145/1536414.1536457.

[Urq87] Alasdair Urquhart. Hard examples for resolution. Journal of the ACM, 34(1):209–
219, 1987. doi:10.1145/7531.8928.

[Wri13] Steve Wright. Quadratic residues and non-residues in arithmetic progression.

Journal of Number Theory, 133(7):2398–2430, 2013. doi:10.1016/[Link].2013.01.004.

[Zha09] Shengyu Zhang. On the tightness of the Buhrman–Cleve–Wigderson simulation. In

Proceedings of the 20th International Symposium on Algorithms and Computation
(ISAAC), volume 5878 of Lecture Notes in Computer Science, pages 434–440.
Springer, 2009. doi:10.1007/978-3-642-10631-6 45.

32