Authors Siu Man Chan, Aaron Potechin,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419
www.theoryofcomputing.org
S PECIAL ISSUE : A NALYSIS OF B OOLEAN F UNCTIONS
Tight Bounds for Monotone Switching
Networks via Fourier Analysis
Siu Man Chan* Aaron Potechin†
Received July 21, 2012; Revised January 22, 2013; Published November 4, 2014
Abstract: We prove tight size bounds on monotone switching networks for the NP-complete
problem of k-clique, and for an explicit monotone problem by analyzing a pyramid structure
of height h for the P-complete problem of generation. This gives alternative proofs of the
separations of m-NC from m-P and of m-NCi from m-NCi+1 , different from Raz–McKenzie
(Combinatorica 1999). The enumerative-combinatorial and Fourier analytic techniques in
this paper are very different from a large body of work on circuit depth lower bounds, and
may be of independent interest.
ACM Classification: F.1.3
AMS Classification: 68Q17, 68Q15, 68Q10
Key words and phrases: lower bounds, space complexity, parallel complexity, monotone complexity,
switching networks, Fourier analysis
1 Introduction
To study parallel time and memory usage complexity, lower bounds are sought in different models of
computation. For example, parallel time is captured by the depth of Boolean circuits of bounded fan-in,
An earlier version of this paper appeared in the Proceedings of the 44th ACM Symp. on Theory of Computing, pages
495–504, 2011.
* This material is based upon work supported by the National Science Foundation under Grant No. CCF-1017403 and Grant
No. CCF-0830797.
† This material is based on work supported by the National Science Foundation Graduate Research Fellowship under Grant
No. 0645960.
© 2014 Siu Man Chan and Aaron Potechin
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2014.v010a015
S IU M AN C HAN AND A ARON P OTECHIN
and memory usage (i. e., space complexity) is captured by the size of switching networks. It is therefore
of interest to prove lower bounds for the depth of Boolean circuits of bounded fan-in, and for the size
of switching networks, for an explicit Boolean function. Unfortunately, lower bounds that separate
complexity classes have not been proved without certain restrictions on the computation.
To prove some lower bounds, researchers often restrict computation to be monotone (i. e., to dis-
allow logical negations in computation) when computing monotone Boolean functions. Improving on
Razborov [48], Alon and Boppana [3] and Haken [26] proved that the clique problem requires polynomial
(nΩ(1) ) depth for monotone circuits.1 In terms of complexity classes, it says
m-NC ⊆ m-P $ m-NP .
This means the clique problem requires high parallel time when computed in a monotone fashion. As
for the parallel time of efficiently computable functions, Karchmer and Wigderson [34] showed that
the directed connectivity problem requires super-logarithmic (Ω(log2 n)) depth for monotone circuits,1
implying
m-NC1 $ m-NL ⊆ m-NC2 .
For more separations, Raz and McKenzie [46] extended the lower bound framework of Karchmer and
Wigderson [34], proving that a monotone circuit1 computing
(1) the complete problem for NL, directed connectivity, requires Ω(log2 n) depth, reproving the tight
bound of Karchmer and Wigderson [34];
(2) the “complete problem for NCi ,” the Generation problem with a pyramid structure of height
h, requires Ω(h log n) depth when h ≤ nc for some constant c > 0, giving m-NC 6= m-P and
m-NCi 6= m-NCi+1 for all i by setting h = logi n; and
(3) the complete problem for NP, the k-clique problem, requires Ω(k log n) depth when k ≤ nc for
some constamt c > 0, improving previous results on cliques for log n k nc .
Much less work has been done on switching networks, which is a combinatorial model capturing
deterministic space-bounded computation (see Section2 for a discussion). Most results are derived using
the connection between circuits and switching networks. Namely, a circuit1 of depth d can be simulated
by a switching network of size 2d , while a switching network of size s can be simulated by a circuit of
depth O(log2 s) [16]. As far as lower bounds go, a bound of Ω(s) for switching network size translates√to
a bound of Ω(log s) for circuit depth, and a bound of Ω(d) for circuit depth translates to a bound of 2Ω( d)
for switching network size. The simulations preserve monotonicity, therefore, so do the translations of
lower bounds.
In particular, from the best lower bounds for the depth of monotone circuits by Raz and McKenzie [46],
it follows that a monotone switching network computing
(1’) directed connectivity requires nΩ(1) size;
√
h/ log n
(2’) the Generation problem with a pyramid structure of height h requires nΩ size when
h ≤ nc for some constant c > 0; and
1 In this paper, we consider only Boolean circuits of fan-in at most two, even when we do not spell it out.
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 390
T IGHT B OUNDS FOR M ONOTONE S WITCHING N ETWORKS VIA F OURIER A NALYSIS
√
k/ log n
(3’) the k-clique problem requires n Ω
size when k ≤ nc for some constant c > 0.
Since a size bound of sΩ(1) for switching networks is equivalent to a space bound of Ω(log s) for Turing
machines,2 item (1’) above is trivial and fails to separate m-L from m-NL for space complexity on the
switching network model.3 Also, items (2’) and (3’) are not effective when, for example, h and k are
O(log n). To match our intuition, we expect that a monotone switching network computing
(1”) directed connectivity requires nΩ(log n) size;
(2”) the Generation problem with a pyramid structure of height h requires nΩ(h) size for h ≤ nc for
some constant c > 0;
(3”) k-clique requires nΩ(k) for k ≤ nc for some constant c > 0.
Note that such bounds for monotone switching networks would in particular imply the above bounds for
monotone circuits by the simulation argument (e. g., (1”) implies (1)).
Recently, Potechin [45] indeed strengthened item (1) to item (1”), i. e., showed that any monotone
switching network solving directed connectivity has quasi-polynomial size, thereby giving m-L 6= m-NL
“on monotone switching networks.”3 To avoid the loss in translation (e. g., from (1) to (1’), as opposed to
(1”)), it is necessary to depart from the circuit-depth lower bound framework of the communication game
by Karchmer and Wigderson [34],4 which is the basis of most previous work on depth complexity of
circuits [15, 19, 22, 25, 29, 33, 34, 46, 47]. Instead, Potechin [45] introduced a Fourier analytic framework
for analyzing extremal instances (minterms and maxterms) of the monotone Boolean function of directed
connectivity.
1.1 Our results
This work extends the Fourier analytic framework [45] to prove tight lower bounds, for (i) an explicit
monotone problem by analyzing a pyramid structure of height h for the P-complete Generation problem,
and for (ii) the NP-complete k-clique problem,5 and as a result strengthens item (2) to item (2”), and
item (3) to item (3”). This strengthens the previous bounds in items (2’) and (3’) for that were translated
from items (2) and (3).
2 Modulo uniformity, of course. The easy direction is folklore (e. g., see [45, §2]), and the hard direction is proved by
Reingold [54].
3 It should be noted that there are at least two combinatorial models for (non-uniform) m-L in the literature: as monotone
(Boolean) circuits (of bounded fan-in) of logarithmic width and polynomial size [24, 25], or as monotone switching networks of
polynomial size [45, 52]. It appears that the two models are not comparable. This work focuses on monotone switching networks
of polynomial size as the combinatorial model for (non-uniform) m-L, and does not imply results for monotone circuits of
logarithmic width and polynomial size as (non-uniform) m-L.
4 Indeed, the Karchmer–Wigderson framework is unlikely to separate m-L from m-NL on monotone switching networks,3
since it is able to prove the same bound of Ω(log2 n) for the depth of monotone circuits solving undirected connectivity [34, 46],
which is in L [54] and computable by monotone switching networks of size n2 . This shows that the quadratic relation between
circuit-depth and (the logarithm of) switching-network-size in the simulation argument of Borodin [16] is tight.
5 To see the matching upper bounds, there are (uniform) monotone switching networks for (i) “the problem computed by the
universal degree-h reversible pebbling switching network” of size nO(h) (see Section3.3.5); and (ii) the k-clique problem of size
kO(1) nO(k) .
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 391
S IU M AN C HAN AND A ARON P OTECHIN
In particular, this gives alternative proofs of the separations of monotone complexity classes like
m-NC 6= m-P and m-NCi 6= m-NCi+1 , using very different arguments compared to Raz–McKenzie [46].6
These monotone separations are necessary for the corresponding non-monotone separations, because a
non-monotone separation (e. g., NC 6= P) implies the corresponding monotone separation (e. g., m-NC 6=
m-P).7 To prove the lower bounds of items (2) and (3), this work simplifies the Fourier analytic framework
of Potechin [45] used for analyzing the directed connectivity problem, by studying invariants in the
Fourier domain (Lemma 3.44 for the generation problem), and by making explicit the role of the invariants
as an inclusion-exclusion principle (see, e. g., Remark 3.39, Lemma 4.14, and Claims 4.16 and 4.17).
Therefore, this work provides a combinatorial understanding of the Fourier analytic framework [45].
Perhaps, more previous results may be strengthened and other problems may be studied by extending
this Fourier/combinatorial framework, as an alternative or a complement to the Karchmer–Wigderson
framework, after three separation results (1), (2) and (3) on monotone circuit-depth are strengthened to
(1”), (2”) and (3”).
1.2 Other related work
We did not discuss other work less relevant to the results presented here, but suggesting lower bounds
to space and parallel complexity [1, 2, 7–9, 18, 21, 39, 41, 43, 51, 53, 59, 60], or implying lower bounds
to monotone depth in general [4, 5, 11, 14, 23, 27, 31, 32, 42, 49, 50, 55–57, 61, 62] or applying monotone
depth to study other complexity measures [12, 13, 28, 35, 37]. For more discussion on the complexity
of monotone Boolean circuits, the reader is referred to [46, §1], and [15, 24]. For more discussion on
switching networks and other models of space-bounded computation, the reader is referred to [52].
We should briefly comment on branching programs, another (more popular) combinatorial model
for studying deterministic space-bounded computation. Nonuniform space is linearly related to (is in Θ
relation with) the logarithm of the size of layered branching program (LBPs), as well as to the logarithm
of the size of switching networks (SNs). (The latter statement depends on Reingold’s theorem [54].)
It follows that for all Boolean functions, SN size and LBP size are polynomially related. However,
no concept of monotone branching programs seems to be known, nor is there an agreed definition of
monotone space complexity. Monotone SNs offer a plausible model of (nonuniform) monotone space
complexity, hence our choice of the model. An alternative model would be width-bounded monotone
circuits; as far as we know, the two models may not be comparable (cf. footnote 3).
1.3 Organization
Section2 collects notions, notation, and conventions used in the introduction and common to Section3
and Section 4. Section 3 treats the generation problem, whose lower bound (item (2”)) is proved
as Theorem 3.46. Section 4 treats the clique problem, whose lower bound (item (3”)) is proved as
Theorem 4.19.
6 This paper further simplifies the proof for the generation problem (item (2”)) in the STOC’12 version.
7 And proving monotone lower bounds is in a sense sufficient, since non-monotone separations would follow from the
monotone lower bounds of some variants of the problems, see, e. g., [21, §4.1].
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 392
T IGHT B OUNDS FOR M ONOTONE S WITCHING N ETWORKS VIA F OURIER A NALYSIS
2 Preliminaries
Recall the Iverson bracket notation: JconditionK to mean 1 if condition is T RUE, and 0 otherwise. Also,
[n] := {0, 1, . . . , n − 1} for n ∈ N. For a Boolean function f : {0, 1}n → {0, 1}, an instance y ∈ {0, 1}n is a
Y ES-instance if f (y) = 1, and a N O-instance if f (y) = 0. A Boolean function is monotone if f (x) ≤ f (y)
whenever x y, i. e., whenever xi ≤ yi for all i ∈ [n]. For a monotone Boolean function f , a minterm
y is a -minimal Y ES-instance, i. e., f (y) = 1 but f (x) = 0 for all x ≺ y; a maxterm y is a -maximal
N O-instance, i. e., f (y) = 0 but f (x) = 1 for all x y.
Following Potechin [45], we denote objects of instances (e. g., variable xi , element u for G EN, vertex
v for C LIQUE) by unprimed letters, and objects of switching networks (e. g., node a0 ∈ V 0 , edge e0 ∈ E 0 )
primed letters.
Definition 2.1 (Switching Networks). Consider a collection x1 , x2 , . . . , xn of Boolean variables.
A switching network G0 has data (V 0 , E 0 , s0 ,t 0 , λ 0 ), where V 0 is the set of nodes and E 0 is the set of
edges of an undirected (multi) graph with two distinguished nodes s0 ,t 0 ∈ V 0 . Each edge e0 ∈ E 0 of G0
is labeled with a literal xi or x̄i with i ∈ [n], specified by λ 0 (e0 ). A switching network is monotone if all
edges are labeled with positive literals (for all e0 , λ 0 (e0 ) = xi for some i).
An instance y ∈ {0, 1}n is accepted by G0 if there is a path P0 connecting s0 and t 0 using edges labeled
with literals in y; namely, P0 =: he01 , e02 , . . . , e0` i, where e0j ∈ E 0 for 1 ≤ j ≤ ` connects v0j−1 and v0j , with
v00 = s0 and v0` = t 0 , satisfying (1) if λ 0 (e0j ) = xi then yi = 1; or (2) λ 0 (e0j ) = x̄i then yi = 0. Otherwise, y is
rejected by G0 . The Boolean function fG0 computed by G0 is identified with the collection of accepted
instances, so fG0 (y) = 1 iff G0 accepts y.
We say that an instance y ∈ {0, 1}n reaches a node a0 ∈ V 0 if there is a path P0 connecting s0 and a0
using edges labeled with literals in y. The undirectedness of a switching network mirrors the reversibility
in deterministic space-bounded computation [40,54].8 Hence switching networks compute by reachability
in a reversible way. The size of a switching network is the number of edges [52].9
We need the following version of Nisan–Wigderson combinatorial design [44]. For a proof and
further references, see [58, Lemma 8].
Lemma 2.2 (Combinatorial Design). For any positive integers q, m, k with k ≤ m, there exist q sets Q1 ,
Q2 , . . . , Qq ⊆ [N] where N := e1+(ln q)/k · (m2 /k), such that |Qi | = m for 1 ≤ i ≤ q and |Qi ∩ Q j | ≤ k for
1 ≤ i < j ≤ q.
3 Lower bound for generation
This section proves the lower bound for (the promise problem of) generation as Theorem 3.46, and uses
it in establishing a tight bound for a monotone decision problem as Theorem 3.48. After defining the
problem and the model below (Definitions 3.1 and 3.2), Section 3.1 introduces a semantic restriction
8 For non-deterministic space-bounded computation, the corresponding model is called a switching-and-rectifier network
(see, e. g., [52]), whose underlying graph can be directed.
9 All lower bounds in this work concern the number of nodes, which is polynomially related to the number of edges here.
Also, constants are not optimized.
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 393
S IU M AN C HAN AND A ARON P OTECHIN
based on reversible pebbling, and Section3.2 proves an optimal lower bound for monotone switching
networks with this restriction. Section3.3 proves a lower bound without this restriction, by reducing the
general case to the reversible pebbling case.
Definition 3.1 (Generation Problem). For a size parameter n, the generation problem (G EN) receives as
input a function e : [n] × [n] × [n] → {0, 1}. Let s := 0 and t := n − 1. We think of s as the source and t as
the target. We say that s generates v ∈ [n] if (1) v is s; or (2) s generates both w and u, and e(w, u, v) = 1.
G EN problem accepts input e if s generates t. The value of e is represented as n3 Boolean variables, and
the positive literal corresponding to e(w, u, v) is suggestively denoted by w ∧ u → v.
The G EN problem is a monotone variant of the first P-complete problem called PATH S YSTEMS [17].
Subproblems of G EN with additional restrictions on e are complete for smaller complexity classes
like non-deterministic logspace (NL) and Nick’s class (NC) [6, 30]. To specialize monotone switching
networks (Definition 2.1) to G EN, we just need to specialize the labeling function λ 0 .
Definition 3.2 (Monotone Switching Networks for G EN). We say that a switching network is a monotone
switching network for G EN (mG EN network), if each edge e0 ∈ E 0 is labeled with λ 0 (e0 ) = w ∧ u → v for
some w, u, v ∈ [n]. For an instance for G EN with input e, the literal λ 0 (e0 ) = w ∧ u → v is in the instance
if e(w, u, v) = 1.
3.1 Reversible pebbling switching networks for generation
As in [45], we begin by considering a simpler class of mG EN networks which are semantically restricted.
In particular, we consider mG EN networks corresponding to the reversible pebble game [10,38], which we
call reversible pebbling mG EN networks (Definition 3.6). In this subsection (and henceforth in this paper),
focus on triples w ∧ u → v where v 6= w and v 6= u, so that a move allowed by w ∧ u → v (Remark 3.3)
corresponds to a reversible pebble move.
Remark 3.3 (Reversible Pebbling for G EN). In the reversible pebble game for G EN, we start with a
pebble on s and try to put a pebble on t. There is only one allowed move:
1. If e(w, u, v) = 1 and both w and u are pebbled, then we may pebble or unpebble v (i. e., add or
remove a pebble on v).10
A configuration K ⊆ [n] of the reversible pebble game specifies the elements that are pebbled.
The idea is that each node a0 ∈ V (G0 ) in a reversible pebbling mG EN network G0 will correspond to
a configuration Ka0 in the reversible pebble game, and each edge e0 ∈ E(G0 ) in G0 with label λ 0 (e0 ) =
w ∧ u → v will correspond to a move in the reversible pebble game which can be done when e(w, u, v) = 1.
However, to make this precise we must first deal with two issues.
The first issue is that the reversible pebble game has many winning configurations (i. e., configurations
in which t is pebbled), but a switching network G0 has only one accepting state t 0 . To fix this, we modify
the reversible pebble game so that all winning configurations are effectively the same.
10 By contrast, any vertex can be unpebbled at any time in standard black pebbling, even when not all of its immediate
predecessors (playing the role of w and u here) are pebbled.
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 394
T IGHT B OUNDS FOR M ONOTONE S WITCHING N ETWORKS VIA F OURIER A NALYSIS
Remark 3.4 (Modified Reversible Pebbling for G EN). In the modified reversible pebble game for G EN,
we start with a pebble on s and try to put a pebble on t. There are two allowed moves:
1. If e(w, u, v) = 1 and both w and u are pebbled, then we may pebble or unpebble v; and
2. If t is pebbled then we may pebble or unpebble any other element x 6= t ∈ [n].
The second issue is that if a sequence of moves can be done when e(w, u, v) = 1, and that sequence
of moves can bring a configuration Ka0 to another configuration Kb0 , then we may as well add an edge
between a0 and b0 with label w ∧ u → v. That is, it makes more sense for an edge e0 in a reversible
pebbling mG EN network G0 with label λ 0 (e0 ) = w ∧ u → v to correspond to a sequence of moves (rather
than a single move) that can be done if e(u, w, v) = 1. This leads to the following definition.
Definition 3.5 (Reversible Pebbling Equivalence). We say that two configurations K1 , K2 ⊆ [n] are l-
equivalent for l := w ∧ u → v if it is possible to bring configuration K1 to configuration K2 using a
sequence of the following moves:
1. If w and u are pebbled, then we may pebble or unpebble v; and
2. If t is pebbled, then we may pebble or unpebble any other element x 6= t ∈ [n].
We can now define reversible pebbling mG EN networks.
Definition 3.6 (Reversible Pebbling Networks). We say that an mG EN network G0 is a reversible pebbling
mG EN network if each node a0 ∈ V 0 can be associated with a reversible pebbling configuration Ka0 ⊆ [n]
satisfying the following conditions:
1. Ks0 = {s} and Kt 0 = [n]; and
2. If there is an edge with label l := w ∧ u → v between nodes a0 and b0 , then Ka0 and Kb0 are l-
equivalent.
Since it is only possible to win the reversible pebble game when t can be generated from s, every
reversible pebbling mG EN network G0 is sound, i. e., if G0 accepts an input e, then e is a Y ES-instance for
G EN. However, it need not compute G EN, since it need not be complete, i. e., accepting all Y ES-instances
of G EN.
Before moving on, we give a more convenient characterization of l-equivalence (Proposition 3.9).
We can do this because the partial order (under set inclusion ⊆) on configurations of the reversible pebble
game for G EN respects l-equivalence, i. e., there is a unique maximal configuration in each l-equivalence
class (Proposition 3.8).
Definition 3.7 (Maximal Configuration). For a configuration K ⊆ [n] and a triple l := w ∧ u → v, define
K + w ∧ u → v to be the ⊆-maximal configuration in the l-equivalence class containing K.
Proposition 3.8 (Maximal Configuration). K + w ∧ u → v is well-defined and
K
if t ∈
/ K, and also w ∈ / K or u ∈
/ K,
K + w ∧ u → v = K ∪ {v} if t ∈ / K, v 6= t, w ∈ K and u ∈ K,
[n] if t ∈ K, or v = t and w ∈ K and u ∈ K.
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 395
S IU M AN C HAN AND A ARON P OTECHIN
Proposition 3.9 (Reversible Pebbling Equivalence). K1 and K2 are l-equivalent for l := w ∧ u → v if and
only if K1 + l = K2 + l.
3.2 Pyramid Y ES-instances and reversible pebbling lower bound
Following Raz and McKenzie [46], consider those Y ES-instances of G EN having a structure of a pyramid
graph.11 Pyramid Y ES-instances of G EN are analogous to path Y ES-instances of directed connectivity
in [45]. In particular, they are minterms of the respective monotone Boolean functions, hence “hardest to
accept.”
Definition 3.10 (Pyramid Graph and Y ES-Instance). For a parameter h, the pyramid graph of height h
has h+12 vertices Vh := {v }
r,c 1≤c≤r≤h . The vertex vr,c is on the r th
row, and Vh is laid out row by row with
the first row on top and the hth row at the bottom. For 1 ≤ r ≤ h − 1, the vertex vr,c has left child vr+1,c
and right child vr+1,c+1 . The pyramid graph is also viewed as a directed graph with arcs pointing from
children to their parents (from vr+1,c to vr,c and from vr+1,c+1 to vr,c ).11
An instance of G EN forms a pyramid Y ES-instance if there exists Q ⊆ [n] \ {s,t} and a bijective
identification P : Q , Vh to vertices Vh of a pyramid graph, and e(w, u, v) = 1 iff (w, u, v) is a triple in
[n] × [n] × [n] consistent with P, meaning that
1. w = u = s and v ∈ Q and P(v) is on the bottom row of Vh ; or
2. w = u ∈ Q and P(w) is on the top row of Vh , and v = t; or
3. w, u, v ∈ Q and P(w) and P(u) are different children of P(v).
In this case, the Y ES-instance is simply called a pyramid, and is denoted by G(P).
Note that the identification P specifies a structure of a pyramid graph over V (P) := Q = P−1 (Vh ) ⊆
[n] \ {s,t} in G(P). Since a reversible pebbling switching network must “pebble vertices one at a time”
(before pebbling t), on any computation path P0 accepting a pyramid G(P), there must be a node b0 ∈ V (P0 )
mentioning lots of vertices of V (P) exclusively, i. e., Kb0 \ {s} ⊆ V (P) and |Kb0 \ {s}| = h (Lemma 3.11).12
Formally, every path from s0 to t 0 on a reversible pebbling mG EN network gives a reversible pebbling
strategy to pebble t, starting from the initial configuration Ks0 (Remark 3.3). Since a reversible pebbling
strategy is also a black pebbling strategy, the lower bound for black pebbling applies also to reversible
pebbling.13
Lemma 3.11 (Barrier Size Bound). Fix a pyramid P of height h. Consider a path P0 =: he01 , e02 , . . . , e0` i
on a reversible pebbling mG EN network, where e0j connects v0j−1 and v0j and is labeled a positive literal
λ 0 (e0j ) ∈ G(P), from s0 := v00 to t 0 := v0` . (Hence Kv0j−1 and Kv0j are l j -equivalent when l j := λ 0 (e0j ) for
1 ≤ j ≤ `.)
If Ks0 = {s} and Kt 0 3 t, then P0 has a node b0 ∈ V (P0 ) with Kb0 \ {s} ⊆ Q and |Kb0 \ {s}| = h.
11 The pyramid graph is routinely used for studying space complexity, especially using pebbling games [17, 36]. We follow
their convention that arcs point from the (r + 1)st row to the rth row.
12 To prove Theorems 3.12 and 3.13, it suffices for b0 to have |K 0 \ {s}| ≥ h, instead of an exact equality.
b
13 The converse (that reversible pebbling number is a lower bound on the black pebbling number) is not true in general. For
example, the line graph (i. e., a single path) having ` edges requires two pebbles in black pebbling, but it takes Θ(log `) pebbles
in reversible pebbling [45].
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 396
T IGHT B OUNDS FOR M ONOTONE S WITCHING N ETWORKS VIA F OURIER A NALYSIS
Proof. By the proof of the black pebbling lower bound for a pyramid graph [17].
Such b0 is a barrier node for P. Note that if two pyramids share less than h vertices, then they must
have different barrier nodes. With this idea, we are ready to prove size lower bounds for reversible
pebbling mG EN networks (Theorems 3.12 and 3.13).
Theorem 3.12 (Reversible Pebbling Lower Bound for G EN). Any reversible pebbling mG EN network G0
1/10
having n0 nodes and computing G EN of size n satisfies n0 ≥ nΘ(n ) .
Proof. Note that G0 accepts all pyramid Y ES-instances. Apply Theorem 3.13.
Theorem 3.13 (Reversible Pebbling Lower Bound for Pyramids). For any 4 ≤ h ≤ n1/10 , any reversible
pebbling mG EN network G0 having n0 nodes for G EN of size n, and accepting all pyramid Y ES-instances
of height h, satisfies n0 ≥ nh/10 = nΘ(h) .
Proof. Fix h, let m := h+1
h/10 , k := h − 1. Then Lemma 2.2 gives q sets Q , Q , . . . , Q ⊆ [N]
2 , q := n 1 2 q
with |Qi | = m and |Qi ∩ Q j | ≤ k for 1 ≤ i 6= j ≤ q, where
h ln n
N ≤ exp + 1 h4 ≤ n1/3 h4 n .
10(h − 1)
For each Qi , construct a pyramid Pi by identifying Qi arbitrarily with a pyramid graph of height h. Now
G(Pi ) is accepted by G0 , via some path Pi0 labeled with positive literals in G(Pi ). Hence Lemma 3.11
gives a node b0i whose reversible pebbling configuration satisfies Kb0i \ {s} ⊆ Qi and |Kb0i \ {s}| = h. Since
|Qi ∩ Q j | ≤ h − 1, we have b0i 6= b0j for 1 ≤ i 6= j ≤ q. Hence n0 ≥ q = nh/10 .
3.3 Lower bound beyond reversible pebbling
For the general lower bound for mG EN networks, we extend the Fourier analysis framework of [45]
(summarized below as Lemma 3.29). Fourier analysis will be done over extremal N O-instances (Defini-
tion 3.14) which can be identified with the Fourier basis (Definition 3.17).
It turns out that any mG EN network computing the generation problem must do non-trivial work per
individual pyramid, and the work will be visible in the Fourier spectrum. The work done for a pyramid P1
will be orthogonal to the work done for a different pyramid P2 if they are well-separated, i. e., P1 and P2
share less than h vertices. Since there are nΘ(h) different pyramids that are pairwise well-separated, an
mG EN network must do an amount of work scaling with nΘ(h) , giving the size lower bound.
3.3.1 Fourier analysis of extremal N O-instances
Let K := {K ⊆ [n] : K 3 s} be the collection of reversible pebbling configurations containing s. A
reversible pebbling configuration Ka0 is proper if Ka0 63 t. Define Ṽ := [n] \ {s,t} and let
C := PowerSet(Ṽ ) := {C : C ⊆ Ṽ }
be the (bi-)colorings of Ṽ . Any C ∈ C can be associated with a subset of [n] containing s but excluding t
by C 7→ C ∪ {s}. This association gives a bijection between C and the sub-collection of the reversible
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 397
S IU M AN C HAN AND A ARON P OTECHIN
pebbling configurations in K not containing t. While the objects in C and K are very different, it will be
convenient to compare them via this bijection, i. e., when writing Ka0 = C or Ka0 ⊆ C, we mean to test for
the associated reversible pebbling configuration, e. g., Ka0 = C ∪ {s} or Ka0 ⊆ C ∪ {s}.
Consider extremal N O-instances for G EN that can be identified with some C ∈ C. Extremal N O-
instances of G EN are analogous to cut N O-instances of directed connectivity in [45].14 In particular, they
are maxterms of respective monotone Boolean functions, hence “hardest to reject.”
Definition 3.14 (Extremal N O-Instances). Any C ∈ C is associated with the extremal N O-instance G(C)
where e(w, u, v) = 0 iff w ∈ C ∪ {s} and u ∈ C ∪ {s} and v ∈/ C ∪ {s} (recall the association mentioned
above). Then the N O-instance G(C) generates v ∈ [n] iff v ∈ C ∪ {s}.15
Proposition 3.15 (Extremal N O-Instances). If Ka0 + l = Kb0 + l and l ∈ G(C), then Ka0 ⊆ C iff Kb0 ⊆ C.16
Proof. If l ∈ G(C), then Ka0 ⊆ C iff Ka0 + l ⊆ C.
The analysis will focus on the collection of extremal N O-instances G(C) = G(C) : C ∈ C .
Definition 3.16 (Inner Product Space of Extremal N O-Instances). A C-vector is a real vector indexed by
C, equivalently a function from C to R. For two C-vectors f and g, we define the inner product
1
h f , gi := ∑ f (C)g(C) ,
|C| C∈C
inducing a norm k f k := h f , f i1/2 .
Definition 3.17 (Fourier Analysis). Given an extremal N O-instance U ∈ C, we define the C-vector
χU (C) := (−1)∑v∈Ṽ Jv∈UKJv∈CK .
Then the collection {χU }U∈C forms an orthonormal basis of the space of all C-vectors, called the Fourier
Basis. For a C-vector g, its Fourier coefficient at U ∈ C is ĝ(U) := hg, χU i.
Let 1 denote the all-ones C-vector: 1(C) = 1 for all C ∈ C; and similarly 0 the all-zeros C-vector.
Note that χ{} = 1.
3.3.2 Invariant cover for generation
This subsection shows how to use Fourier analysis to obtain size lower bounds on sound mG EN networks
(Lemma 3.29). We begin by assigning C-vectors to the nodes of mG EN networks.
14 Similar considerations of extremal N O -instances appeared also in Raz–McKenzie [46], although the extremal N O -instances
they considered are not maxterms in their setting.
15 This implies that G(C) are all maxterms of G EN . To see this, given any N O -instance G of G EN , consider C := set of
elements (except s) generated by G, then G ⊆ G(C) (when comparing the set of positive literals).
16 Recall that we write K 0 = C and K 0 ⊆ C to mean K 0 = C ∪ {s} and K 0 ⊆ C ∪ {s} when comparing a reversible pebbling
a a a a
configuration Ka0 ∈ K with a bi-coloring C ∈ C.
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 398
T IGHT B OUNDS FOR M ONOTONE S WITCHING N ETWORKS VIA F OURIER A NALYSIS
Definition 3.18 (Annotated mG EN Networks). A function description of an mG EN network G0 is a
function F : V 0 → RC (i. e., an assignment of a C-vector Fa0 to each a0 ∈ V 0 ). A function description F is
valid for G0 if:
1. Fs0 = 1 and Ft 0 = 0; and
2. If a0 and b0 are connected by an edge labeled l, where l ∈ G(C), then Fa0 (C) = Fb0 (C).
An annotated mG EN network is an mG EN network G0 together with a valid function description F for G0 .
A standard valid function description for a sound mG EN network is reachability, defined below.
Definition 3.19 (Reachability). Fix an mG EN network G0 . For a0 ∈ V 0 , let Ra0 (C) := T RUE if the
extremal N O-instance G(C) can reach a0 .17 The Boolean vector Ra0 is identified with the C-vector
Ra0 (C) := JC can reach a0 K.
Note that Rs0 = 1; and if G0 is sound, then Rt 0 = 0.
Proposition 3.20 (Adjacent Reachability). If a0 and b0 are connected by an edge labeled l, where l ∈ G(C),
then Ra0 (C) = Rb0 (C).
Lemma 3.21 (Valid Function Description). An mG EN network G0 has a valid function description if and
only if G0 is sound.
Proof. If G0 is sound, then the reachability vector assignment R is a valid function description for it. If G0
is not sound, then G0 accepts some N O-instance G(C) for some C ∈ C (because G(C) are all maxterms of
G EN),15 via some path P0 connecting s0 and t 0 labeled with literals in G(C). If F is a function description
for G0 satisfying the adjacency condition (item (2)) in Definition 3.18, then for any two adjacent a0 and b0
on V (P0 ), Fa0 (C) = Fb0 (C). Thus Fs0 (C) = Ft 0 (C) and F cannot be valid for G0 .
We now introduce our key tool, invariant covers (Definition 3.23).
Definition 3.22 (l-Invariant). For a literal l and an annotated mG EN network G0 (with a valid function
description F), a C-vector g is l-invariant on G0 if for any a0 and b0 in V (G0 ) connected by an edge labeled
l, hFa0 , gi = hFb0 , gi. We say that g is l-invariant if g is l-invariant on G0 for any annotated mG EN network
G0 .
Definition 3.23 (Invariant Cover). Consider a Y ES instance P. A collection of C-vectors {gP,ι }ι∈I over
some index set I forms an invariant cover (for P) if (1) for any positive literal l ∈ G(P), there is an ι ∈ I
so that gP,ι is l-invariant; and (2) for any ι ∈ I, we have h1, gP,ι i = 1.
The idea behind invariant covers is as follows. For each ι ∈ I, item (2) of Definition 3.23 implies
hFs0 , gP,ι i = 1 and hFt 0 , gP,ι i = 0. Consider a path P0 connecting s0 and t 0 , all of whose edges are labeled
with literals from P. As we move from s0 to t 0 along P0 , imagine that for each ι ∈ I there is a player trying
to get hFv0 , gP,ι i from 1 to 0, where v0 is the current node on P0 . Whenever we move across an edge e0
on P0 with label λ 0 (e0 ) = l, the players may all make progress towards this goal, except for the players
17 Hence R 0 is the truth table at node a0 restricted to the extremal N O -instances G(C).
a
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 399
S IU M AN C HAN AND A ARON P OTECHIN
ι ∈ I such that gP,ι is l-invariant, who can make no progress. Since l ∈ G(P), item (1) of Definition 3.23
ensures that at least one player cannot make progress. This implies that at some node b0 on P0 , there will
be a large discrepancy in progress among the players (Lemma 3.25), i. e., hFb0 , gP,ι1 − gP,ι2 i will be large
for some ι1 , ι2 ∈ I. Such a node b0 is called a barrier node. If the C-vectors gP,ι are chosen carefully, this
implies a large size lower bound (Lemma 3.29). This is made precise below (and the argument is phrased
in terms of reachability R, the standard valid function description).
Lemma 3.24 (Barrier). Fix a Y ES instance P with an invariant cover {gP,ι }ι∈I for P. Consider a
path P0 =: he01 , e02 , . . . , e0` i labeled with literals from P (that is, e0j connects v0j−1 and v0j and is labeled
λ 0 (e0j ) ∈ G(P)) from s0 := v00 to t 0 := v0` . If Rs0 = 1 and Rt 0 = 0, then there is a node b0 on P0 , and distinct
ι1 , ι2 ∈ I, such that
1
|hRb0 , gP,ι1 − gP,ι2 i| ≥ .
`−1
Proof. Apply Lemma 3.25 with d j,ι := hRv0j , gP,ι i.
Lemma 3.25 (Discrepancy in Progress). Consider real numbers d j,ι ∈ R for integer 0 ≤ j ≤ ` and for
index ι ∈ I. If (1) for all ι ∈ I, d0,ι = 1 and d`,ι = 0, and (2) for any 0 < j ≤ `, there is ι j ∈ I such that
d j−1,ι j = d j,ι j , then there exist j and distinct η, ι ∈ I, such that
1
|d j,η − d j,ι | ≥ .
`−1
Proof. For 0 ≤ j ≤ `, let m j := minι d j,ι and M j := maxι d j,ι and s j := M j − m j (s stands for stretch or
span). Assumption (2) implies that m j−1 ≤ M j = m j + s j . Assumption (1) gives m` = s` = 0,
1 = m0 ≤ m` + ∑ s j = ∑ sj ,
0< j≤` 0< j<`
1
and s j ≥ `−1 for some 0 < j < `.
We need a simple fact concerning the support of Fourier coefficients (Proposition 3.28), based on
Definitions 3.26 and 3.27. The orthogonality in Fourier support gives the orthogonality in work done to
different pyramids.
Definition 3.26 (Fourier Support). For a pyramid P, say a C-vector g is P-supported if
1. g depends only on coloring in P, i. e., g(C1 ) = g(C2 ) if v ∈ C1 ⇔ v ∈ C2 for all v ∈ V (P); or
equivalently
2. ĝ(U) 6= 0 only when U ⊆ V (P).
Definition 3.27 (High Frequency Support). We introduce cut-off degree and agreement degree for
describing the Fourier support.
1. A C-vector g has cut-off degree k if ĝ(U) 6= 0 only when |U| ≥ k.
2. A collection of C-vectors {gι }ι∈I agrees up to degree k if for all U ∈ C where |U| ≤ k, we have
ĝι1 (U) = ĝι2 (U) for ι1 , ι2 ∈ I.
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 400
T IGHT B OUNDS FOR M ONOTONE S WITCHING N ETWORKS VIA F OURIER A NALYSIS
Proposition 3.28 (Cut-Off and Agreement). For a collection of C-vectors {gι }ι∈I , the following are
equivalent:
1. for any ι1 , ι2 ∈ I, the difference gι1 − gι2 has cut-off degree k + 1; and
2. {gι }ι∈I agrees up to degree k.
Later, we will construct an invariant cover agreeing up to degree k = Ω(h) and of “length” σ ≤
O(k log n) (with a small enough constant in O(·)), giving a size lower bound of 2Ω(h log n) = nΩ(h) via
Lemma 3.29.
Lemma 3.29 (Size Lower Bound from Invariant Cover). For h ≤ n1/8 , if there is an invariant cover
{gP,ι }ι∈I for a pyramid
Y ES-instance P ofσheight h such that (1) gP,ι is P-supported, (2)0 {gP,ι }ι∈I 0agrees
h+1
up to degree k ≤ 2 , and (3) kgP,ι k ≤ 2 for ι ∈ I; then any sound mG EN network G having n nodes
for G EN of size n and accepting all pyramid Y ES-instances, satisfies
n0 ≥ 2(k log n)/40−(σ +1)/2 .
Proof. Fix a pyramid P of height h. Its Y ES instance G(P) is accepted by G0 via some path P0 labeled
with literals from G(P). Lemma 3.24 gives a node b0P and a C-vector gP := gP,ι1 − gP,ι2 such that
|hRb0P , gP i| ≥ 1/n0 . Note that kgP k ≤ kgP,ι1 k + kgP,ι2 k ≤ 2σ +1 . Also, gP has cut-off degree k + 1 by
Proposition 3.28, and is P-supported.
Let q := nk/10 , m := h+1
2 , then Lemma 2.2 gives q sets Q1 , Q2 , . . . , Qq ⊆ [N] satisfying |Qi | = m and
|Qi ∩ Q j | ≤ k for 1 ≤ i 6= j ≤ q, where
2
k ln n m
N = exp +1 ≤ en1/10 m2 n .
10k k
For each Qi , construct a pyramid Pi by identifying Qi arbitrarily with a pyramid graph of height h. Now the
previous paragraph gives b0i := b0Pi and gi := gPi . Normalize g̃i := gi /kgi k, then {g̃i }1≤i≤q is orthonormal
(having disjoint Fourier support). Note that 1 ≥ kRb0 k2 ≥ ∑i |hRb0 , g̃i i|2 for any b0 ∈ V 0 . Now
1 2
n0 = ∑ 1 ≥ ∑ ∑ |hRa0 , g̃i i|2 ≥ ∑|hRb0i , g̃i i|2 ≥ q 0 σ +1 ,
a0 ∈V 0 i a0 ∈V 0 i n2
since
1 1 1
|hRb0i , g̃i i| ≥ ≥ .
n0 kgi k n0 2σ +1
It follows that (n0 )3 ≥ q/22σ +2 = nk/10 /22σ +2 .
3.3.3 Reduction to reversible pebbling
This subsection reuses the lower bound for reversible pebbling mG EN networks (Lemma 3.11) for
constructing invariant covers. Recall that each C-vector gP,ι in an invariant cover is l-invariant for some
literal (triple) l. Note that being l-invariant is a strong condition: gP,ι must satisfy a linear algebraic relation
with respect to any mG EN network. However, it turns out that l-invariant vectors can be constructed using
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 401
S IU M AN C HAN AND A ARON P OTECHIN
a single mG EN network (Definition 3.31 and Corollary 3.36), which is even a reversible pebbling mG EN
network. Indeed, G0P (Definition 3.31) is suitable for this task, because “any reversible pebbling strategy
to pebble P can be lifted to, or seen as a subgraph (i. e., edge subset) of, G0P with a matching function
description K.” Hence the name universal.
Definition 3.30 (ζ -Function18 ). Identify a reversible pebbling configuration Ka0 ∈ K with the C-vector
Ka0 (C) := JKa0 ⊆ CK for C ∈ C.16
Definition 3.31 (Universal Reversible Pebbling Switching Network). Given a pyramid P, consider G0P :=
(VP , EP , sP ,tP , λP ) where VP := PowerSet V (P) ∪ {Kt 0 } ⊆ K is the collection of all proper reversible
0 0 0 0 0 0
pebbling configurations over elements of P, plus the improper reversible pebbling configuration Kt 0 := [n].
Hence each a0 ∈ VP0 is identified and naturally associated with its reversible pebbling configuration (i. e.,
Ka0 := a0 ∪ {s} ∈ K as in Definition 3.6), with the obvious distinguished nodes s0P and tP0 so that Ks0P = Ks0
and KtP0 = Kt 0 . Now a0 and b0 in VP0 are connected by an edge e0 in EP0 with label a triple λP0 (e0 ) = l ∈ G(P)
iff Ka0 + l = Kb0 + l. Then G0P is a reversible pebbling mG EN network annotated with a valid function
description K : VP0 → RC (Definition 3.18 and Proposition 3.15).
To construct invariants (Definition 3.22) using the universal network (Definition 3.31), we need an
alternative, equivalent characterization of invariants (Lemma 3.33) concerning the spatial19 support of
C-vectors (Definition 3.32).
Definition 3.32 (l-Definite). For a literal l, say that a C-vector g is l-definite if g(C) 6= 0 implies l ∈ G(C)
(Definition 3.14).
Lemma 3.33 (Invariant ⇔ Definite). g is l-invariant iff g is l-definite.
Proof. For the ⇐ direction, on any annotated mG EN network G0 with a valid function description F,
when a0 and b0 are connected by an edge labeled l, Fa0 (C)g(C) = Fb0 (C)g(C) for any C, because either
(i) g(C) = 0, or (ii) l ∈ G(C), hence Fa0 (C) = Fb0 (C) (item 2 of Definition 3.18). The ⇒ direction follows
from Lemma 3.34.
The following proof of Lemma 3.34, i. e., backward induction and Lemma 3.35, was communicated
to us by Yuval Filmus and Robert Robere, substantially simplifying proofs and presentations in earlier
versions.
Lemma 3.34 (Reversible Pebbling Invariant). If g is l-invariant on G0P , then g is l-definite.
/ G(C) and g is l-invariant on G0P , then g(C) = 0 by a backward induction on C as follows.
Proof. If l ∈
Note that v ∈
/ C if l =: w ∧ u → v ∈
/ G(C), and
g(C) = ∑ g(D) − ∑ g(D) .
C⊆D⊆Ṽ \{v} C⊂D⊆Ṽ \{v}
The first term is zero by Lemma 3.35, and the second term is also zero if (1) C = Ṽ \ {v} vacuously, or
(2) g(D) = 0 for all C ⊂ D ⊆ Ṽ \ {v} by induction hypothesis.
18 The C-vector K 0 (·) can be identified with ζ (a0 , ·) of the incidence algebra over the partially ordered set C of proper
a
0
reversible pebbling configurations. For a fixed pyramid P, the corresponding inverse ga (·) (see Proposition 3.40) can basically
0
be identified with µ(·, a ), interpreting the inner product h·, ·i (Definition 3.16) as a convolution (Proposition 3.40).
19 Spatial as in spatial domain, as the dual to frequency domain.
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 402
T IGHT B OUNDS FOR M ONOTONE S WITCHING N ETWORKS VIA F OURIER A NALYSIS
Lemma 3.35 (Inclusion-Exclusion Principle). If g is l-invariant on G0P , and l =: w ∧ u → v ∈
/ G(C), then
∑C⊆D⊆Ṽ \{v} g(D) = 0.
Proof. Let a0 := C and b0 := C ∪ {v}, then a0 and b0 are connected by an edge labeled l on G0P , for
C + l = C ∪ {v}. Since g is l-invariant on G0P , hKa0 , gi = hKb0 , gi. Hence
0 = |C|hg, Ka0 − Kb0 i = ∑ g(D) Ja0 ⊆ DK − Jb0 ⊆ DK =
∑ g(D) .
D C⊆D⊆Ṽ \{v}
Corollary 3.36 (Reversible Pebbling Invariant). g is l-invariant iff g is l-invariant on G0P .
Proof. The ⇐ direction follows from Lemma 3.34 and the ⇐ direction of Lemma 3.33.
3.3.4 Invariant cover from the universal network
For the many properties required in the lower bound framework (Lemma 3.29) concerning Fourier
support, Corollary 3.36 intuitively handles the condition of l-invariance (implicit in an invariant cover).
Other properties are easier to satisfy than l-invariance, except perhaps the property of agreement, which
is handled by the notion of l-accessible reversible pebbling configurations (Definition 3.38) relative to
a barrier (Definition 3.37). Roughly, different l-accessible reversible pebbling configurations A0l (for
different literals l) agree with each other over the common accessible reversible pebbling configurations
A0 , which translates to the agreement condition (see Lemma 3.41).
Definition 3.37 (Barrier). Consider a set of nodes B0 ⊆ VP0 . A path P0 on G0P intersects B0 if V (P0 ) ∩ B0 6=
{}. A collection of reversible pebbling configurations B0 ⊂ VP0 is a barrier if s0P ∈
/ B0 and tP0 ∈
/ B0 and every
0 0 0 0
path P from sP to tP on GP intersects B .0
Definition 3.38 (l-Accessible Reversible Pebbling Configurations). Relative to a barrier B0 ⊂ VP0 , we
define the collection of accessible reversible pebbling configurations
A0 := a0 ∈ VP0 : ∃ a path P0 connecting s0P and a0 and P0 does not intersect B0 .
We want an extended notion of l-accessible reversible pebbling configurations A0l ⊇ A0 where we allow
intersection caused by edges labeled l, defined by
A0l := a0 ∈ VP0 : a0 ∈ A0 or a0 is adjacent to b0 ∈ A0 by an edge labeled l .
That is, all edges crossing A0l are not labeled with l. Indeed, if a0 is adjacent to b0 ∈ A0 by an edge
labeled l =: w ∧ u → v, then a0 and b0 differ by a reversible pebbling move (Remark 3.3) to pebble or
unpebble v, since t is not involved if b0 ∈ A0 . It follows that if a0 and b0 are connected by an edge labeled
l =: w ∧ u → v, and a0 ∈ A0l , then b0 ∈ A0l as well (they differ at most by a reversible pebbling move
(Remark 3.3) to pebble or unpebble v).
Remark 3.39 (Möbius Inversion). To construct an invariant cover {gP,l }l∈G(P) (Lemma 3.41) where
each gP,l is P-supported (for use in Lemma 3.29), it suffices to restrict attention to P-supported vectors,
which form a subspace of C-vectors. Note that the C-vector Ka0 is P-supported iff a0 ⊆ V (P) = Q
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 403
S IU M AN C HAN AND A ARON P OTECHIN
(Definition 3.30), i. e., if Ka0 is over elements of P. Since Ka0 (·) = ζ (a0 , ·), the collection {Ka0 }a0 ⊆V (P) can
be identified with the ζ -function of (the incidence algebra over) the partially ordered set PowerSet V (P)
of proper reversible pebbling configurations over elements of P. Hence {Ka0 }a0 ⊆V (P) forms a basis for the
0 0
subspace of P-supported C-vectors, admitting a dual basis {gb }b0 ∈V (P) satisfying hKa0 , gb i = Ja0 = b0 K
(Proposition 3.40),16 given by an inclusion-exclusion over PowerSet V (P) (i. e., a Möbius inversion).
0
Hence if gP,l := ∑a0 ∈A0l ga , then hKb0 , gP,l i = Jb0 ∈ A0l K, indicating whether b0 ∈ A0l . Thus for any a0 and b0
on G0P connected by an edge labeled l, it follows that hKa0 , gP,l i = Ja0 ∈ A0l K = Jb0 ∈ A0l K = hKb0 , gP,l i by
the construction of A0l (Definition 3.38). So gP,l is l-invariant on G0P , hence l-invariant (Corollary 3.36).
Proposition 3.40 (Dual Vector to Ka0 ). Fix a subset Q = V (P) ⊆ Ṽ ⊂ [n] of size |Q|. We write C̄ := C ∩ Q
0
for C ∈ C. For any subset a0 ⊆ Q, define a P-supported C-vector ga by
0 0
ga (C) := 2|Q| JC̄ ⊆ a0 K(−1)|a |−|C̄| .
0 0 0 0
Then (1) hKb0 , ga i = Ja0 = b0 K for a0 , b0 ⊆ Q;16 and (2) ĝa (U) = (−2)|a | Ja0 ⊆ UK. In particular, ĝa is
0
supported on U ⊇ a0 , i. e., ĝa (U) 6= 0 only when U ⊇ a0 .
0
Proof. Note that ga is P-supported by definition, hence
0 1 0 1 0 0
hKb0 , ga i = ∑ Kb0 (C)ga (C) = |Q| ∑ Kb0 (C̄)ga (C̄) = ∑ (−1)|a |−|C̄| = Ja0 = b0 K ,
|C| C∈C 2 C̄⊆Q b0 ⊆C̄⊆a0
0
on observing that (−1)|a |−|C̄| = µ(C̄, a0 ) is the µ-function of (the incidence algebra over) the partially
0
ordered set PowerSet V (P) . Thus (1) holds. For (2), since ga is P-supported, focus on U ⊆ Q, then
0 0 0
ĝa (U) = hχU , ga i = ∑ (−1)|C̄∩U|+|a |−|C̄| ,
C̄⊆a0
0 0
which is zero (due to cancellation) unless a0 ⊆ U, in which case it gives ∑C̄⊆a0 (−1)|a | = (−2)|a | .
Lemma 3.41 (Constructing Invariants). For any pyramid P of height h ≥ 2, let m := h+1
2 , for any
positive literal l ∈ G(P), there is a C-vector gP,l such that (1) gP,l is P-supported, (2) gP,l is l-invariant,
(3) h1, gP,l i = 1, (4) for all U ⊆ Ṽ where |U| ≤ k := h − 1, we have ĝP,l (U) is independent of l,20 (5) for
all U ⊆ Ṽ , |ĝP,l (U)| ≤ 2τ where τ := 2h log(em/h), and (6) kgP,l k ≤ 2σ where σ := m/2 + τ.
Proof. Let B0 := a0 ∈ VP0 \ {tP0 } : |Ka0 \ {s}| = h be the collection of reversible pebbling configurations
(on the universal reversible pebbling switching network G0P ) having exactly h vertices on V (P), which
is a barrier by Lemma 3.11. Let A0l be the l-accessible reversible pebbling configurations relative to
B0 . Note that tP0 ∈ / A0l since h h+1 a0 a0
2 . Now let gP,l := ∑a0 ∈Al g , where g is the dual vector to Ka
0 0
a0
(Proposition 3.40). Each g is P-supported, hence (1) holds. The end of Remark 3.39 establishes (2). For
0 0
(3), note that 1 = χ{} and ĝa ({}) 6= 0 only when a0 = s0P , and ĝsP ({}) = 1 (Proposition 3.40). For (4), note
that if a0 is such that |Ka0 \ {s}| < h, then a0 ∈ A0l iff a0 ∈ A0 , hence Ja0 ∈ A0l K = Ja0 ∈ A0 K is independent
20 A collection
gP,l (U) l is independent of l if gP,l1 (U) = gP,l2 (U) for any l1 , l2 .
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 404
T IGHT B OUNDS FOR M ONOTONE S WITCHING N ETWORKS VIA F OURIER A NALYSIS
0
of l for such a0 . Also note that ĝa (U) 6= 0 only when a0 ⊆ U by Proposition 3.40. For (5), note that if
a0 ∈ A0l , then |Ka0 \ {s}| ≤ h. Also recall
h em h
m m
:= ∑ ≤ .
≤h i=0 i h
0
Since ĝP,l (U) = ∑a0 ∈A0l ĝa (U),
em h
a0 |a0 | m
ĝP,l (U) ≤ ∑ ĝ (U) ≤ ∑ 2 ≤ 2h ≤ 2h = 2h log(em/h)+h .
a0 ∈A0l a0 ∈A0l
≤h h
using Proposition 3.40. For (6), hgP,l , gP,l i = ∑U⊆Q ĝP,l (U)2 ≤ 2m 22τ .
3.3.5 Tight size bound
Note that the lower bound (Lemma 3.29) gets stronger as the invariant cover gets shorter (having a smaller
σ ). And for tight size bounds (Theorems 3.46 and 3.48), the first term Θ(k log n) has to dominate the
second term Θ(σ ). To this end, we need yet another alternative, equivalent characterization of invariants
(Definition 3.22) concerning Fourier support (Lemma 3.44). This characterization allows us to chop off
high frequency Fourier coefficients from gP,l to shorten the vectors (Lemma 3.45). Recall that we focus
on literals l = w ∧ u → v where w 6= v and u 6= v. Further, assume w 6= t and u 6= t and v 6= s, which is the
case for our analysis (Lemma 3.29) and would simplify the treatment in Lemma 3.44.
Propositions 3.42 and 3.43 are simple facts about representing Boolean logic in Fourier analysis.
Proposition 3.42 (Arithmetization). Fix v ∈ [n]. Define the C-vectors αv and βv by
1 1
2 χ{} (C) − χ{v} (C) if v ∈ Ṽ ,
2 χ{} (C) + χ{v} (C) if v ∈ Ṽ ,
αv (C) := χ{} (C) if v = s, and βv (C) := 0 if v = s,
0 if v = t. χ{} (C) if v = t.
Then for any C ∈ C, we have Jv ∈ C ∪ {s}K = αv (C) and Jv ∈
/ C ∪ {s}K = βv (C).
Proposition 3.43 (Orbital Average). For Z ⊆ Ṽ and v ∈ Ṽ \ Z, define Zv := Z ∪ {v}, then
(χ{} − χ{v} ) ĝ(Z)χZ + ĝ(Zv )χZv = ĝ(Z) − ĝ(Zv ) (χZ − χZv )
and
(χ{} + χ{v} ) ĝ(Z)χZ + ĝ(Zv )χZv = ĝ(Z) + ĝ(Zv ) (χZ + χZv ) .
Proof. When v ∈
/ Z, we have χZv (C) = χZ (C)χ{v} (C), so (under co-ordinate-wise multiplication)
χ{} − χ{v} χZ = χZ − χZv = χ{v} − χ{} χZv ,
giving the first equality. The second equality is proved similarly.
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 405
S IU M AN C HAN AND A ARON P OTECHIN
Lemma 3.44 (Fourier Invariant). Fix a triple l := w ∧ u → v. Let ψ(l) := {w, u, v} ∩ Ṽ . A C-vector g is
l-invariant iff for any Z ⊆ Ṽ \ ψ(l), we have
0 = ξg,l (Z) := ∑ χṼ ∩{w,u} (X)ĝ(Z ∪ X) .
X⊆ψ(l)
Proof. g is l-invariant iff g is l-definite (Lemma 3.33) iff g(C) = Jl ∈ G(C)Kg(C) for all C ∈ C (Defi-
nition 3.32). If l = w ∧ u → v for w, u, v ∈ [n], then Jl ∈ G(C)K = 1 − Jw ∈ Cs KJu ∈ Cs KJv ∈
/ Cs K where
Cs := C ∪ {s} (Definition 3.14). Therefore, for any C ∈ C, we have
g(C) = Jl ∈ G(C)Kg(C) iff Jw ∈ Cs KJu ∈ Cs KJv ∈
/ Cs Kg(C) = 0 .
Succinctly, g is l-invariant iff (under co-ordinate-wise multiplication)
Jw ∈ · ∪ {s}KJu ∈ · ∪ {s}KJv ∈
/ · ∪ {s}Kg = 0
as C-vectors, iff (by Proposition 3.42) αw αu βv g = 0 as C-vectors. Fourier expand g as
g = ∑ ĝ(U)χU = ∑ ∑ ĝ(Z ∪Y )χZ∪Y . (3.1)
U⊆Ṽ Z⊆Ṽ \ψ(l) Y ⊆ψ(l)
Now g is l-invariant iff (under co-ordinate-wise multiplication as C-vectors)
0 = αw αu βv ∑ ∑ ĝ(Z ∪Y )χZ∪Y ,
Z⊆Ṽ \ψ(l) Y ⊆ψ(l)
which (by Proposition 3.43, recall w 6= t, u 6= t, v 6= s) is equivalent to
0= ∑ ∑ Ṽ ∩{w,u}
χ (X) ĝ(Z ∪ X) (Y )χ
∑ Ṽ ∩{w,u} Z∪Y
χ
Z⊆Ṽ \ψ(l) X⊆ψ(l) Y ⊆ψ(l)
= ∑ ξg,l (Z)η(Z) ,
Z⊆Ṽ \ψ(l)
where η(Z) := ∑Y ⊆ψ(l) χṼ ∩{w,u} (Y )χZ∪Y . Note that η(Z) Z are orthogonal and non-zero, hence linearly
independent.
Lemma 3.45 (Low-Pass Invariant). Fix natural numbers k and τ. If for a pyramid P, for any posi-
tive literal l ∈ G(P), there is a C-vector gP,l such that (1) gP,l is P-supported, (2) gP,l is l-invariant,
(3) h1, gP,l i = 1, (4) for all U ⊆ Ṽ where |U| ≤ k, we have ĝP,l (U) is independent of l,20 and (5) for all
U ⊆ Ṽ , |ĝP,l (U)| ≤ 2τ ; then for any positive literal l ∈ G(P), there
is a C-vector g̃P,l satisfying (1), (2),
(3), (4), and (5), plus (6) kg̃P,l k ≤ 2 where σ := (k + 4) log m + τ.
σ
Proof. For l ∈ G(P), expand gP,l = ∑C∈C ĝP,l (C)χC as a C-vector. If l =: w ∧ u → v, define
Cl,k := C ∈ C : |C \ ψ(l)| ≤ k ⊆ C
for ψ(l) := Ṽ ∩ {w, u, v}, and g̃P,l := ∑C∈Cl,k ĝP,l (C)χC as a C-vector by chopping off the high frequency
Fourier coefficients from gP,l . Note that hg̃P,l , χU i 6= 0 implies hgP,l , χU i 6= 0 for any U ∈ C. Now g̃P,l
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 406
T IGHT B OUNDS FOR M ONOTONE S WITCHING N ETWORKS VIA F OURIER A NALYSIS
is P-supported due to the second item of Definition 3.26, hence (1) holds. Since gP,l is l-invariant, by
Lemma 3.44, ξg,l (Z) = 0 for any Z ⊆ Ṽ \ ψ(l). It follows that ξg̃,l (Z) = 0 for any such Z, as either (i) for
some X ⊆ ψ(l), Z ∪ X ∈ Cl,k , hence Z ∪ X ∈ Cl,k for all such X, thus ξg̃,l (Z) = ξg,l (Z); or (ii) for all
X ⊆ ψ(l), Z ∪ X ∈ / Cl,k , thus ξg̃,l (Z) = 0. So g̃P,l is l-invariant by Lemma 3.44 and (2) holds. For (3),
1 = χ{} and hg̃P,l , χ{} i = hgP,l , χ{} i. For (4), when U ⊆ Ṽ has |U| ≤ k, hg̃P,l , χU i = hgP,l , χU i. (5) follows
since |hg̃P,l , χU i| ≤ |hgP,l , χU i| for all U ⊆ Ṽ . Note that |C| ≤ k + 3 for C ∈ Cl,k , hence
m
hg̃P,l , g̃P,l i = ∑ ĝ2P,l (C) ≤ 22τ ≤ m2k+6 22τ .
C∈Cl,k ≤ k + 3
Theorem 3.46 (Size Lower Bound). For any 4 ≤ h ≤ n1/600 , any sound mG EN network G0 having n0
nodes for G EN of size n, and accepting all pyramid Y ES-instances of height h, satisfies
n0 ≥ 2(h log n)/400−1/2 = nΘ(h) .
Proof. By Lemma 3.41, boosted by Lemma 3.45, there is an invariant cover {gP,l }l∈G(P) for P such
that (1) gP,l is P-supported and (2) {gP,l }l∈G(P) agrees up to degree k := h − 1, and (3) kgP,l k ≤ 2σ with
σ ≤ (k + 4) log m + 4h log m ≤ 6h log m. Now Lemma 3.29 gives
k 1 1 h 1 h 1
log n0 ≥ log n − σ − ≥ log n − 3h log m − ≥ log n − .
40 2 2 80 2 400 2
Theorem 3.46 gives a size lower bound for mG EN networks solving the generation problem, by
analyzing pyramid Y ES-instances. However, the general generation problem may be harder and require
larger mG EN networks. To get a tight bound (and thus defending the title of this paper), we construct below
a monotone (decision) problem computed by a (uniform) mG EN network (Definition 3.47), allowing us
to reuse Theorem 3.46 for a tight size bound in Theorem 3.48.
Definition 3.47 (Universal Degree-h Reversible Pebbling Switching Network). For a size parameter n
and h ≤ n, consider
G0n,h := (Vh0 , Eh0 , s0h ,th0 , λh0 )
where
Ṽ
Vh0 :=
∪ Kt 0 := V ⊆ [n] \ {s,t} : |V | ≤ h ∪ {Kt 0 }
≤h
is the collection of proper reversible pebbling configurations of size at most h (excluding s), plus the
improper reversible pebbling configuration. Hence each a0 ∈ Vh0 is identified and naturally associated
with its reversible pebbling configuration (Ka0 := a0 ∪ {s} ∈ K as in Definition 3.6), with the obvious
distinguished nodes s0h and th0 so that Ks0h = Ks0 and Kth0 = Kt 0 . Now a0 and b0 in Vh0 are connected by an
edge e0 in Eh0 labeled with a triple λh0 (e0 ) = l iff Ka0 + l = Kb0 + l. Then G0n,h is a reversible pebbling mG EN
network annotated with a valid function description K : VP0 → RC (Definition 3.18 and Proposition 3.15).
Recall that fG0n,h is the function computed by G0n,h , which is monotone. Note that G0n,h has
n−2
+ 1 = nO(h)
≤h
nodes (and hence nO(h) edges).
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 407
S IU M AN C HAN AND A ARON P OTECHIN
Theorem 3.48 (Tight Size Bound). For any 12 ≤ h ≤ 3n1/600 , any mG EN network G0 having n0 nodes
and computing fG0n,h satisfies
1
n0 ≥ nh/1200 = nΘ(h) .
2
Proof. Note that G0n,h is sound and accepts all pyramid Y ES-instances of height h/3 (by simulating a
reversible pebbling strategy), and so is any G0 computing fG0n,h . Now apply Theorem 3.46.
4 Lower bound for cliques
This section proves the lower bound for cliques as Theorem 4.19. After defining the problem and
the model below (Definitions 4.1 and 4.2), Section4.1 introduces the Fourier analytic framework over
extremal N O-instances, Section4.2 describes the lower bound framework assuming the existence of an
invariant cover, and Section 4.3 constructs the invariant cover. These subsections clearly share many
similarities with the lower bound proof in Section3.
Definition 4.1 (Clique Problem). For a size parameter n, let V := [n] be n vertices. For 2 ≤ k ≤ n, the
k-clique problem (k-C LIQUE) receives as input a subset E ⊆ V2 of edges. k-C LIQUE accepts input E
i. e., if there is U ⊆ V , |U| = k, and {u, v} ∈ E for all u 6= v ∈ U. The
if the graph (V, E) has a k-clique,
n
value of E is represented as 2 Boolean variables.
Definition 4.2 (Monotone Switching Networks for C LIQUE). We say that a switching network is a
monotone switching network for C LIQUE (mC LIQUE network), if each edge e0 ∈ E 0 is labeled with
λ 0 (e0 ) = {u, v} for some u 6= v ∈ V . Given an instance for k-C LIQUE with data E, the literal λ 0 (e0 ) = {u, v}
is in the instance if {u, v} ∈ E.
4.1 Fourier analysis on extremal instances
The analysis focuses on the Y ES-instances of C LIQUE having a structure of a k-clique, and the N O-
instances that are (k − 1)-colorable.21 In particular, those Y ES-instances are minterms and those N O-
instances are ‘similar’ to maxterms of C LIQUE as a monotone Boolean function, and they are respectively
“hardest to accept” and “hardest to reject.” Fourier analysis will be done on the truth tables restricted to
the (k − 1)-colorable instances (Definition 4.7). These definitions for C LIQUE are analogous to the ones
for G EN in Section3.3.1.
n
Definition 4.3 (k-clique Y ES-Instances). An instance G(P) ∈ {0, 1}(2) of C LIQUE forms a k-clique
Y ES-instance if there exists Q ⊆ V , |Q| = k such that {u, v} ∈ E iff u 6= v and u, v ∈ Q. In this case, the
Y ES-instance is simply called a k-clique (also denoted by P), and V (P) := Q ⊆ V .
Definition 4.4 (Extremal N O-Instances). Let C := C : V → [k − 1] ∼ V
= [k − 1] be the collection of k − 1
colorings of V . A coloring C ∈ C is associated with the extremal N O-instance G(C) where an edge
{u, v} ∈
/ G(C) iff C(u) = C(v) for u, v ∈ V .
21 This consideration is standard in the study of the monotone complexity of k-C LIQUE (e. g., [46, 55]), and similar ideas date
back at least to Razborov [48].
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 408
T IGHT B OUNDS FOR M ONOTONE S WITCHING N ETWORKS VIA F OURIER A NALYSIS
Definition 4.5 (Inner Product Space of Colorings). A C-vector is a complex vector with index set C,
equivalently a function from C to C. For two C-vectors f and g, we define
1
h f , gi := ∑ f (C)g(C)
|C| C∈C
as their inner product, inducing the norm k f k := h f , f i1/2 . Then CC is an inner product space.
Definition 4.6 (Fourier Analysis). For a coloring U ∈ C, we define the C-vector
χU (C) := ω ∑v∈V U(v)C(v) ,
where ω := ωk−1 := e2πi/(k−1) is the primitive (k − 1)st root of unity. The collection {χU }U∈C forms
an orthonormal basis for CC , called the Fourier Basis. We write ĝ(U) := hg, χU i to denote the Fourier
coefficient of g at “frequency” U. We say that the support of U is supp(U) := {v ∈ V : U(v) 6= 0} for
U ∈ C.
Definition 4.7 (Reachability). Fix an mC LIQUE network G0 . For a0 ∈ V 0 , let Ra0 (C) := T RUE if the
extremal N O-instance G(C) can reach a0 .22 The Boolean vector Ra0 is identified with the C-vector
Ra0 (C) := JC can reach a0 K.
Proposition 4.8 (Adjacent Reachability). If a0 and b0 are connected by an edge labeled {u, v}, where
{u, v} ∈ G(C), then Ra0 (C) = Rb0 (C).
Let 1 denote the all-ones C-vector: 1(C) = 1 for all C ∈ C; and similarly 0 the all-zeros C-vector.
Note that Rs0 = 1; and if G0 is sound (i. e., does not accept N O-instances), then Rt 0 = 0.
4.2 Invariant cover for cliques
This subsection adapts the framework of invariant cover from G EN to C LIQUE as Lemma 4.13, by
suitably changing the definitions of an invariant cover (Definitions 4.9 and 4.10) and Fourier support
(Definitions 4.11 and 4.12).
Definition 4.9 (l-Invariant). For a literal l and an mC LIQUE network G0 , a C-vector g is l-invariant on
G0 if for any a0 and b0 in V (G0 ) connected by an edge labeled l, hRa0 , gi = hRb0 , gi. We say that g is
l-invariant if g is l-invariant on G0 for any mC LIQUE network G0 .
Definition 4.10 (Invariant Cover). Consider a Y ES instance P. A collection of C-vectors {gP,ι }ι∈I over
some index set I forms an invariant cover (for P) if (1) for any positive literal l ∈ G(P), there is an ι ∈ I
so that gP,ι is l-invariant; and (2) for any ι ∈ I, we have h1, gP,ι i = 1.
Definition 4.11 (Fourier Support). For a k-clique P, say a C-vector g is P-supported if
1. g depends only on coloring in P, i. e., g(C1 ) = g(C2 ) if C1 (v) = C2 (v) for all v ∈ V (P); or equiva-
lently
22 Hence R 0 is the truth table at node a0 restricted to the extremal N O -instances G(C).
a
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 409
S IU M AN C HAN AND A ARON P OTECHIN
2. ĝ(U) 6= 0 only when supp(U) ⊆ V (P).
Definition 4.12 (High Frequency Support). We introduce cut-off degree and agreement degree for
describing the Fourier support.
1. A C-vector g has cut-off degree k if ĝ(U) 6= 0 only when |supp(U)| ≥ k.
2. A collection of C-vectors {gι }ι∈I agrees up to degree k if for all U ∈ C where |supp(U)| ≤ k, we
have ĝι1 (U) = ĝι2 (U) for ι1 , ι2 ∈ I.
Lemma 4.13 (Size Lower Bound from Invariants). For 3 ≤ k ≤ n1/100 , if there is an invariant cover
{gP,ι }ι∈I such that (1) gP,ι is P-supported, (2) {gP,ι }ι∈I agrees up to degree k − 2, and (3) kgP,ι k ≤ kk ;
then any sound mC LIQUE network G0 having n0 nodes for C LIQUE of size n and accepting all k-cliques,
satisfies
n0 ≥ (1/2)nk/100 = nΘ(k) .
Proof. Fix a k-clique P. Its Y ES-instance G(P) is accepted by G0 via some path P0 labeled with edges
from G(P). Lemma 3.24 gives a node b0P and a C-vector gP := gP,ι1 − gP,ι2 such that |hRb0P , gP i| ≥ 1/n0 .23
Note that kgP k ≤ kgP,u k + kgP,v k ≤ 2kk . Also, gP has cut-off degree k − 1 by Proposition 3.28, and is
P-supported.
Let q := nk/10 , then Lemma 2.2 gives q sets Q1 , Q2 , . . . , Qq ⊆ [N] satisfying |Qi | = k and |Qi ∩ Q j | ≤
k − 2 for 1 ≤ i 6= j ≤ q, where
2
k ln n k
N = exp +1 ≤ n1/3 k2 n .
10(k − 2) k−2
For each Qi , construct the k-clique Pi with V (Pi ) = Qi , then the previous paragraph gives b0i := b0Pi and
gi := gPi . Normalize g̃i := gi /kgi k, then {g̃i }1≤i≤q is orthonormal (having disjoint Fourier support). Note
that 1 ≥ kRb0 k2 ≥ ∑i |hRb0 , g̃i i|2 for any b0 ∈ V 0 . Now
1 2
n0 = ∑ 1 ≥ ∑ ∑ |hRa0 , g̃i i|2 ≥ ∑|hRb0i , g̃i i|2 ≥ q ,
a0 ∈V 0 i a0 ∈V 0 i n0 2kk
since
1 1 1
|hRb0i , g̃i i| ≥ 0
≥ 0 k.
n kgi k n 2k
It follows that
q nk/10 1 k/20
(n0 )3 ≥ = ≥ n .
4k2k 4k2k 4
23 Strictly speaking, C-vectors in Section4.1 are complex vectors while C-vectors in Section3.3.1 are real vectors. We may
redefine C-vectors in Section3.3.1 as complex vectors. In doing so, the only necessary change is the proof of Lemma 3.24: we
may apply Lemma 3.25 instead with d j,ι := real part of hRv0j , gP,ι i.
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 410
T IGHT B OUNDS FOR M ONOTONE S WITCHING N ETWORKS VIA F OURIER A NALYSIS
4.3 Constructing invariant cover
This subsection constructs an invariant cover for C LIQUE (Lemma 4.14) by exploiting the symmetry in
the problem. The lower bound for C LIQUE is proved as Theorem 4.19.
Fix a collection of vertices D (e. g., V (P) ∼
= [k]) and a color set R (e. g.,[k − 1]). A coloring C : D → R
has a monopoly if exactly one color class has more than one vertex, i. e., c ∈ R : |C−1 (c)| > 1 = 1, in
which case the monopoly refers to vertices in D with the dominating color. Later, for counting purposes,
we will restrict attention to a subset of vertices in a clique, e. g., D = [k − 2] and R = [k − 1]. In such
cases, say C is proper if C(u) = C(v) implies u = v for u, v ∈ D.
Lemma 4.14 (Invariant Cover). Define the scaling factor φ (k) := (k − 1)k−1 /(k − 2)!(k − 2). For any
vertex v in a k-clique P, define a C-vector gP,v by
if C (restricted to P) has a monopoly with τ vertices
φ (k)(−1)τ (τ − 2)!
gP,v (C) := and the monopoly does not contain v,
0 otherwise.
Then (1) gP,v is P-supported, (2) gP,v is l-invariant when l = {u, v} for any u ∈ V (P) \ {v}, (3) h1, gP,v i = 1,
(4) {gP,v }v∈P agrees up to degree k − 2, and (5) kgP,v k ≤ kk/2 .
Proof. Item (1) is clear. For (2), note that if gP,v (C) 6= 0 then C gives a unique color to v in P, i. e.,
C(u) 6= C(v) for all u ∈ V (P) \ {v}. Hence if a0 and b0 are connected by an edge labeled l = {u, v}
where u ∈ V (P) \ {v}, then Ra0 (C)gP,v (C) = Rb0 (C)gP,v (C) for any C, because either (i) gP,v (C) = 0, or
(ii) C(u) 6= C(v), then {u, v} ∈ G(C) and Ra0 (C) = Rb0 (C) (Proposition 4.8).
For (3), note that when C gives v a unique color
(denoted by cv below) in P, ignoring v and its color
reduces to a coloring C̃ : V (P) \ {v} → [k − 1] \ C(v) , which is identified with C̃ : [k − 1] → [k − 2].
For τ ≥ 2, the number of such C̃ having a monopoly of size τ is
k − 1 (k − 2)!
,
τ (τ − 2)!
hence
1 k − 1 (k − 2)!
h1, gP,v i = |C|−1 ∑ gP,v (C) = ∑ ∑ · φ (k)(−1)τ (τ − 2)!
C∈C (k − 1)k c ∈[k−1] 2≤τ≤k−1 τ (τ − 2)!
v
1 k−1
= ∑ (−1)τ = 1,
k − 2 2≤τ≤k−1 τ
using the combinatorial identity ∑0≤τ≤t τt (−1)τ = 0 for t ≥ 1.24
For (4), note that C-vectors g1 and g2 agree up to degree k − 2 if they “depend the same way on
colorings whose domain has size at most k − 2” (Claim 4.15). More precisely, introduce the following.
24 Elchanan Mossel noticed that this implicit use of the principle of inclusion-exclusion for controlling Fourier coefficients is
similar to the Efron-Stein decomposition [20].
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 411
S IU M AN C HAN AND A ARON P OTECHIN
For nesting vertex sets D1 ⊇ D2 , a coloring C1 : D1 → R extends a coloring C2 : D2 → R if C1 agrees
with C2 when restricted to D2 , i. e., C1 (v) = C2 (v) for v ∈ D2 . Define
Ext(C2 , D1 ) := {C1 : D1 → R extending C2 }
as all extensions of C2 to D1 . The C2 -slice of a C-vector g is slice(g,C2 ) := |E|−1 ∑C1 ∈E g(C1 ), where
E := Ext(C2 , D1 ) with an appropriate D1 (which will be clear from the context, e. g., V or V (P)).
Claim 4.15 (Agreement). C-vectors g1 and g2 agree up to degree k − 2 if slice(g1 ,C2 ) = slice(g2 ,C2 ) for
any coloring C2 : D2 → [k − 1] such that |D2 | ≤ k − 2.
Proof. Given any coloring U ∈ C as frequency, partition C by colors over supp(U), and rewrite
ĝ(U) = |C|−1 ∑ g(C)χU (C) = |S|−1 ∑ slice g, S χU (S) ,
C∈C S∈S
where S := S : supp(U) → [k − 1] is the collection of colorings over the support of U (note that χU
depends only on colors over supp(U)). Hence if |supp(U)| ≤ k − 2, then
ĝ1 (U) = |S|−1 ∑ slice g1 , S χU (S) = |S|−1 ∑ slice g2 , S χU (S) = ĝ2 (U) .
S∈S S∈S
Hence (4) follows, if for any u, v ∈ V (P), we have slice(gP,u ,C2 ) = slice(gP,v ,C2 ) for any coloring
C2 : D2 → [k − 1] with |D2 | ≤ k − 2. Further, we can assume D2 ⊆ V (P), since gP,u and gP,v are P-
supported. Therefore, after computing the slice function (Claim 4.16) to show the independence of v
(Claim 4.17), item (4) follows from Claim 4.18 (due to Claim 4.15).
Claim 4.16 (Indicator of Proper Coloring). If D2 ⊆ V (P) has size |D2 | = k − 1, and D2 3 v, then for any
coloring C2 : D2 → [k − 1], we have
k−2
slice(gP,v ,C2 ) = φ (k)JC2 is properK .
k−1
Proof. Let E := Ext C2 ,V (P) , then any extension C1 ∈ E colors one more vertex w ∈ V (P) \ D2 than
C2 , and
1
slice(gP,v ,C2 ) = slice(gP,v ,C1 ) .
k − 1 C∑
1 ∈E
If C2 is proper, then by considering the coloring of w,
1. one extension C1 ∈ E has a monopoly of size 2 containing v, where slice(gP,v ,C1 ) = 0; and
2. k − 2 extensions C1 ∈ E has a monopoly of size 2 not containing v, where slice(gP,v ,C1 ) = φ (k) as
(−1)2 (2 − 2)! = 1.
Thus
k−2
slice(gP,v ,C2 ) = φ (k)
k−1
if C2 is proper.
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 412
T IGHT B OUNDS FOR M ONOTONE S WITCHING N ETWORKS VIA F OURIER A NALYSIS
Otherwise, C2 is not proper, and has a color class with more than one vertex. If C2 does not have
a monopoly or the monopoly contains v, then any extension C ∈ Ext(C2 ,V ) has gP,v (C) = 0, hence
slice(gP,v ,C2 ) = 0.
For the remaining case, C2 has a monopoly of size τ ≥ 2 not containing v. By considering the coloring
of w,
• one extension C1 ∈ E has a monopoly of size τ + 1 not containing v, where slice(gP,v ,C1 ) =
φ (k)(−1)τ+1 (τ − 1)!; and
• τ − 1 extensions C1 ∈ E have a monopoly of size τ not containing v, where slice(gP,v ,C1 ) =
φ (k)(−1)τ (τ − 2)!.
Hence
φ (k)
slice(gP,v ,C2 ) = (−1)τ+1 (τ − 1)! + (τ − 1)(−1)τ (τ − 2)! = 0 .
k−1
Claim 4.17 (Independence of v). If D2 ⊆ V (P) has size |D2 | = k − 2, then for any coloring C2 : D2 →
[k − 1], we have
k−2
slice(gP,v ,C2 ) = φ (k)JC2 is properK ,
(k − 1)2
which is independent of v.
Proof. Let D1 be an arbitrary subset such that D1 ⊆ V (P) and |D1 | = k − 1 and D1 ⊇ D2 ∪ {v}. Now
slice(gP,v ,C2 ) = |E|−1 ∑C1 ∈E slice(gP,v ,C1 ) where E := Ext(C2 , D1 ). If C2 is not proper, neither is any
C1 ∈ E, hence slice(gP,v ,C1 ) = 0 by Claim 4.16, and slice(gP,v ,C2 ) = 0. Otherwise C2 is proper, then
exactly one extension C1 ∈ E is proper, and the result follows from Claim 4.16.
Claim 4.18 (Equality of Slices). For any C2 : D2 → [k − 1] with D2 ⊆ V (P) and |D2 | ≤ k − 2, we have
slice(gP,u ,C2 ) = slice(gP,v ,C2 ) for any u, v ∈ V (P).
Proof. Let D1 be an arbitrary subset of size |D1 | = k − 2 such that D2 ⊆ D1 ⊆ V (P). Let E :=
Ext(C2 , D1 ), then Claim 4.17 gives slice(gP,u ,C1 ) = slice(gP,v ,C1 ) for C1 ∈ E, so
slice(gP,u ,C2 ) = |E|−1 ∑ slice(gP,u ,C1 ) = |E|−1 ∑ slice(gP,v ,C1 ) = slice(gP,v ,C2 ) .
C1 ∈E C1 ∈E
To compute kgP,v k for (5), partition C by coloring to v (denoted by cv below),
−1 2 1 k − 1 (k − 2)! 2
hgP,v , gP,v i = |C| ∑ gP,v (C) = k ∑ ∑ · φ (k)(−1)τ (τ − 2)!
C∈C (k − 1) c ∈[k−1] 2≤τ≤k−1 τ (τ − 2)!
v
(k − 1)k−1
k − 1 (τ − 2)!
= 2 ∑ ≤ (k − 1)k ,
(k − 2) 2≤τ≤k−1 τ (k − 2)!
since
k − 1 (τ − 2)!
≤ k −1.
τ (k − 2)!
So kgP,v k ≤ kk/2 .
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 413
S IU M AN C HAN AND A ARON P OTECHIN
Theorem 4.19 (Size Lower Bound). For 3 ≤ k ≤ n1/100 , any mC LIQUE network G0 having n0 nodes and
computing k-C LIQUE of size n, satisfies
1
n0 ≥ nk/100 = nΘ(k) .
2
Proof. Use Lemmas 4.13 and 4.14.
Acknowledgements
We thank Yuval Filmus and Robert Robere for pointing out an error in an earlier version, and for
substantially simplifying the conceptual framework with a backward induction of Lemma 3.35. The
first-named author thanks Anand Bhaskar, Stephen Cook, Pierre McKenzie, Thomas Watson, and Dustin
Wehr for helpful discussions. We also thank the anonymous reviewers of STOC’12 and the anonymous
reviewers of ToC and their colleagues, for valuable comments on presentations.
References
[1] M IKLÓS A JTAI: A non-linear time lower bound for Boolean branching programs. Theory of
Computing, 1(8):149–176, 2005. Preliminary version in FOCS’99. [doi:10.4086/toc.2005.v001a008]
392
[2] M IKLÓS A JTAI , L ÁSZLÓ BABAI , P ÉTER H AJNAL , J ÁNOS KOMLÓS , PAVEL P UDLÁK , VOJTECH
R ÖDL , E NDRE S ZEMERÉDI , AND G YÖRGY T URÁN: Two lower bounds for branching programs.
In Proc. 18th STOC, pp. 30–38. ACM Press, 1986. [doi:10.1145/12130.12134] 392
[3] N OGA A LON AND R AVI B. B OPPANA: The monotone circuit complexity of Boolean functions.
Combinatorica, 7(1):1–22, 1987. [doi:10.1007/BF02579196] 390
[4] K AZUYUKI A MANO AND A KIRA M ARUOKA: The potential of the approximation
method. SIAM J. Comput., 33(2):433–447, 2004. Preliminary version in FOCS’96.
[doi:10.1137/S009753970138445X] 392
[5] A LEXANDER E. A NDREEV: On a method for obtaining lower bounds for the complexity of
individual monotone functions. Soviet Mathematics Doklady, 31(3):530–534, 1985. 392
[6] DAVID A. M IX BARRINGTON AND P IERRE M C K ENZIE: Oracle branching programs and
Logspace versus P. Inform. and Comput., 95(1):96–115, 1991. Preliminary version in MFCS’89.
[doi:10.1016/0890-5401(91)90017-V] 394
[7] DAVID A. M IX BARRINGTON AND H OWARD S TRAUBING: Superlinear lower bounds for bounded-
width branching programs. J. Comput. System Sci., 50(3):374–381, 1995. Preliminary version in
SCT’91. [doi:10.1006/jcss.1995.1029] 392
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 414
T IGHT B OUNDS FOR M ONOTONE S WITCHING N ETWORKS VIA F OURIER A NALYSIS
[8] PAUL B EAME , T HATHACHAR S. JAYRAM , AND M ICHAEL E. S AKS: Time-space tradeoffs for
branching programs. J. Comput. System Sci., 63(4):542–572, 2001. Preliminary version in FOCS’98.
[doi:10.1006/jcss.2001.1778] 392
[9] PAUL B EAME , M ICHAEL E. S AKS , X IAODONG S UN , AND E RIK V EE: Time-space trade-off
lower bounds for randomized computation of decision problems. J. ACM, 50(2):154–195, 2003.
Preliminary version in FOCS’00. [doi:10.1145/636865.636867] 392
[10] C HARLES H. B ENNETT: Time/space trade-offs for reversible computation. SIAM J. Comput.,
18(4):766–776, 1989. [doi:10.1137/0218053] 394
[11] C HRISTER B ERG AND S TAFFAN U LFBERG: Symmetric approximation arguments for
monotone lower bounds without sunflowers. Comput. Complexity, 8(1):1–20, 1999.
[doi:10.1007/s000370050017] 392
[12] M ARÍA L UISA B ONET, J UAN L UIS E STEBAN , N ICOLA G ALESI , AND JAN J OHANNSEN:
On the relative complexity of resolution refinements and cutting planes proof systems.
SIAM J. Comput., 30(5):1462–1484, 2000. Preliminary versions in FOCS’98 and ECCC.
[doi:10.1137/S0097539799352474] 392
[13] M ARÍA L UISA B ONET, T ONIANN P ITASSI , AND R AN R AZ: Lower bounds for cutting planes
proofs with small coefficients. J. Symbolic Logic, 62(3):708–728, 1997. Preliminary version in
STOC’95. JSTOR. 392
[14] R AVI B. B OPPANA: Threshold functions and bounded depth monotone circuits. J. Comput. System
Sci., 32(2):222–229, 1986. Preliminary version in STOC’84. [doi:10.1016/0022-0000(86)90027-9]
392
[15] R AVI B. B OPPANA AND M ICHAEL S IPSER: The complexity of finite functions. In Handbook of
Theoretical Computer Science, Volume A: Algorithms and Complexity (A), pp. 757–804. Elsevier
and MIT Press, 1990. [ACM:114886] 391, 392
[16] A LLAN B ORODIN: On relating time and space to size and depth. SIAM J. Comput., 6(4):733–744,
1977. [doi:10.1137/0206054] 390, 391
[17] S TEPHEN A. C OOK: An observation on time-storage trade off. J. Comput. System Sci., 9(3):308–
316, 1974. Preliminary version in STOC’73. [doi:10.1016/S0022-0000(74)80046-2] 394, 396,
397
[18] S TEPHEN A. C OOK , P IERRE M C K ENZIE , D USTIN W EHR , M ARK B RAVERMAN , AND R AHUL
S ANTHANAM: Pebbles and branching programs for tree evaluation. ACM Trans. Com-
putation Theory, 3(2):4:1–4:43, 2012. Preliminary versions in FSTTCS’09 and MFCS’09.
[doi:10.1145/2077336.2077337] 392
[19] J EFF E DMONDS , RUSSELL I MPAGLIAZZO , S TEVEN RUDICH , AND J I ŘÍ S GALL: Communication
complexity towards lower bounds on circuit depth. Comput. Complexity, 10(3):210–246, 2001.
Preliminary version in FOCS’91. [doi:10.1007/s00037-001-8195-x] 391
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 415
S IU M AN C HAN AND A ARON P OTECHIN
[20] B RADLEY E FRON AND C HARLES S TEIN: The jackknife estimate of variance. Ann. Stat., 9(3):586–
596, 1981. [doi:10.1214/aos/1176345462] 411
[21] A NNA G ÁL , M ICHAL KOUCKÝ , AND P IERRE M C K ENZIE: Incremental branching programs.
Theory Comput. Syst., 43(2):159–184, 2008. Preliminary versions at Complexity of Boolean
Functions and CSR’06. [doi:10.1007/s00224-007-9049-y] 392
[22] M IKAEL G OLDMANN AND J OHAN H ÅSTAD: A simple lower bound for monotone clique us-
ing a communication game. Inform. Process. Lett., 41(4):221–226, 1992. [doi:10.1016/0020-
0190(92)90184-W] 391
[23] M IKAEL G OLDMANN AND J OHAN H ÅSTAD: Monotone circuits for connectivity have depth
(log n)2−o(1) . SIAM J. Comput., 27(5):1283–1294, 1998. Preliminary version in STOC’95.
[doi:10.1137/S0097539795285631] 392
[24] M ICHELANGELO G RIGNI: Structure in Monotone Complexity. Ph. D. thesis, Massachusetts Institute
of Technology, 1991. Available at CiteSeerX. [ACM:918937] 391, 392
[25] M ICHELANGELO G RIGNI AND M ICHAEL S IPSER: Monotone separation of logarithmic space from
logarithmic depth. J. Comput. System Sci., 50(3):433–437, 1995. Preliminary version in SCT’91.
[doi:10.1006/jcss.1995.1033] 391
[26] A RMIN H AKEN: Counting bottlenecks to show monotone P 6= NP. In Proc. 36th FOCS, pp. 36–40.
IEEE Comp. Soc. Press, 1995. [doi:10.1109/SFCS.1995.492460] 390
[27] DANNY H ARNIK AND R AN R AZ: Higher lower bounds on monotone size. In Proc. 32nd
STOC, pp. 378–387. ACM Press, 2000. Full version available at author’s home page.
[doi:10.1145/335305.335349] 392
[28] RUSSELL I MPAGLIAZZO , T ONIANN P ITASSI , AND A LASDAIR U RQUHART: Upper and lower
bounds for tree-like cutting planes proofs. In Proc. 9th Ann. Symp. on Logic in Computer Science
(LICS’94), pp. 220–228. IEEE Comp. Soc. Press, 1994. [doi:10.1109/LICS.1994.316069] 392
[29] JAN J OHANNSEN: Depth lower bounds for monotone semi-unbounded fan-in circuits. RAIRO -
Theoretical Informatics and Applications, 35(3):277–286, 2001. [doi:10.1051/ita:2001120] 391
[30] N EIL D. J ONES AND W ILLIAM T. L AASER: Complete problems for deterministic polynomial time.
Theor. Comput. Sci., 3(1):105–117, 1976. Preliminary version in STOC’74. [doi:10.1016/0304-
3975(76)90068-2] 394
[31] S TASYS J UKNA: Finite limits and monotone computations: The lower bounds criterion.
In Proc. 12th IEEE Conf. on Computational Complexity (CCC’97), pp. 302–313, 1997.
[doi:10.1109/CCC.1997.612325] 392
[32] M AURICIO K ARCHMER: On proving lower bounds for circuit size. In Proc. 8th IEEE Conf.
on Structure in Complexity Theory (SCT’93), pp. 112–118. IEEE Comp. Soc. Press, 1993.
[doi:10.1109/SCT.1993.336535] 392
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 416
T IGHT B OUNDS FOR M ONOTONE S WITCHING N ETWORKS VIA F OURIER A NALYSIS
[33] M AURICIO K ARCHMER , R AN R AZ , AND AVI W IGDERSON: Super-logarithmic depth lower
bounds via the direct sum in communication complexity. Comput. Complexity, 5(3-4):191–204,
1995. Preliminary version in SCT’91. [doi:10.1007/BF01206317] 391
[34] M AURICIO K ARCHMER AND AVI W IGDERSON: Monotone circuits for connectivity require super-
logarithmic depth. SIAM J. Discrete Math., 3(2):255–265, 1990. Preliminary version in STOC’88.
[doi:10.1137/0403021] 390, 391
[35] M AURICIO K ARCHMER AND AVI W IGDERSON: On span programs. In Proc. 8th IEEE Conf. on
Structure in Complexity Theory (SCT’93), pp. 102–111, 1993. [doi:10.1109/SCT.1993.336536] 392
[36] M ARIA M. K LAWE: A tight bound for black and white pebbles on the pyramid. J. ACM, 32(1):218–
228, 1985. Preliminary version in FOCS’83. [doi:10.1145/2455.214115] 396
[37] JAN K RAJÍ ČEK: Interpolation theorems, lower bounds for proof systems, and independence results
for bounded arithmetic. J. Symbolic Logic, 62(2):457–486, 1997. JSTOR. 392
[38] R ICHARD K RÁLOVIC: Time and space complexity of reversible pebbling. RAIRO - Theoret-
ical Informatics and Applications, 38(2):137–161, 2004. Preliminary version in SOFSEM’01.
[doi:10.1051/ita:2004008] 394
[39] M ATTHIAS K RAUSE: Lower bounds for depth-restricted branching programs. Inform. and Comput.,
91(1):1–14, 1991. [doi:10.1016/0890-5401(91)90072-A] 392
[40] K LAUS -J ÖRN L ANGE , P IERRE M C K ENZIE , AND A LAIN TAPP: Reversible space equals deter-
ministic space. J. Comput. System Sci., 60(2):354–367, 2000. Preliminary version in CCC’97.
[doi:10.1006/jcss.1999.1672] 393
[41] K ETAN M ULMULEY: Lower bounds in a parallel model without bit operations. SIAM J. Comput.,
28(4):1460–1509, 1999. [doi:10.1137/S0097539794282930] 392
[42] K ATSUTOSHI NAKAYAMA AND A KIRA M ARUOKA: Loop circuits and their relation to Razborov’s
approximation model. Inform. and Comput., 119(2):154–159, 1995. [doi:10.1006/inco.1995.1083]
392
[43] È DUARD I VANOVI Č N E ČIPORUK: On a Boolean function. Soviet Mathematics Doklady, 7(4):999–
1000, 1966. 392
[44] N OAM N ISAN AND AVI W IGDERSON: Hardness vs randomness. J. Comput. System Sci., 49(2):149–
167, 1994. [doi:10.1016/S0022-0000(05)80043-1] 393
[45] A ARON P OTECHIN: Bounds on monotone switching networks for directed connectivity. In Proc.
51st FOCS, pp. 553–562. IEEE Comp. Soc. Press, 2010. An updated version to appear in Journal of
the ACM. [doi:10.1109/FOCS.2010.58] 391, 392, 393, 394, 396, 397, 398
[46] R AN R AZ AND P IERRE M C K ENZIE: Separation of the monotone NC hierarchy. Combinatorica,
19(3):403–435, 1999. Preliminary version in FOCS’97. [doi:10.1007/s004930050062] 390, 391,
392, 396, 398, 408
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 417
S IU M AN C HAN AND A ARON P OTECHIN
[47] R AN R AZ AND AVI W IGDERSON: Monotone circuits for matching require linear depth. J. ACM,
39(3):736–744, 1992. Preliminary version in STOC’90. [doi:10.1145/146637.146684] 391
[48] A LEXANDER A. R AZBOROV: Lower bounds for the monotone complexity of some Boolean
functions. Soviet Mathematics Doklady, 31(2):354–357, 1985. 390, 408
[49] A LEXANDER A. R AZBOROV: Lower bounds on monotone complexity of the logical perma-
nent. Mathematical Notes of the Academy of Sciences of the USSR, 37(6):485–493, 1985.
[doi:10.1007/BF01157687] 392
[50] A LEXANDER A. R AZBOROV: On the method of approximations. In Proc. 21st STOC, pp. 167–176.
ACM Press, 1989. [doi:10.1145/73007.73023] 392
[51] A LEXANDER A. R AZBOROV: Lower bounds of the complexity of symmetric Boolean functions of
contact-rectifier circuits. Mathematical Notes of the Academy of Sciences of the USSR, 48(6):1226–
1234, 1990. [doi:10.1007/BF01240265] 392
[52] A LEXANDER A. R AZBOROV: Lower bounds for deterministic and nondeterministic branching
programs. In 8th Internat. Symp. on Fundamentals of Computation Theory, 8th International
Symposium (FCT’91), pp. 47–60, 1991. [doi:10.1007/3-540-54458-5_49] 391, 392, 393
[53] A LEXANDER A. R AZBOROV, AVI W IGDERSON , AND A NDREW C HI -C HIH YAO: Read-once
branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus.
Combinatorica, 22(4):555–574, 2002. Preliminary version in STOC’97. [doi:10.1007/s00493-002-
0007-7] 392
[54] O MER R EINGOLD: Undirected connectivity in log-space. J. ACM, 55(4):17:1–17:24, 2008. Prelim-
inary version in STOC’05. [doi:10.1145/1391289.1391291] 391, 392, 393
[55] B ENJAMIN ROSSMAN: The monotone complexity of k-clique on random graphs. In Proc. 51st
FOCS, pp. 193–201. IEEE Comp. Soc. Press, 2010. [doi:10.1109/FOCS.2010.26] 392, 408
[56] JANOS S IMON AND S HI -C HUN T SAI: On the bottleneck counting argument. Theoret. Comput. Sci.,
237(1-2):429–437, 2000. Preliminary version in CCC’97. [doi:10.1016/S0304-3975(99)00321-7]
392
[57] É VA TARDOS: The gap between monotone and non-monotone circuit complexity is exponential.
Combinatorica, 8(1):141–142, 1988. [doi:10.1007/BF02122563] 392
[58] L UCA T REVISAN: Extractors and pseudorandom generators. J. ACM, 48(4):860–879, 2001.
Preliminary version in STOC’99. [doi:10.1145/502090.502099] 393
[59] D USTIN W EHR: Pebbling and branching programs solving the tree evaluation problem. Technical
report, 2010. [arXiv:1002.4676] 392
[60] D USTIN W EHR: Lower bound for deterministic semantic-incremental branching programs solving
GEN. Technical report, 2011. [arXiv:1101.2705] 392
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 418
T IGHT B OUNDS FOR M ONOTONE S WITCHING N ETWORKS VIA F OURIER A NALYSIS
[61] A NDREW C HI -C HIH YAO: Circuits and local computation. In Proc. 21st STOC, pp. 186–196. ACM
Press, 1989. [doi:10.1145/73007.73025] 392
[62] A NDREW C HI -C HIH YAO: A lower bound for the monotone depth of connectivity. In Proc. 35th
FOCS, pp. 302–308. IEEE Comp. Soc. Press, 1994. [doi:10.1109/SFCS.1994.365685] 392
AUTHORS
Siu Man Chan
Postdoc Department of Computer Science
University of Toronto
siuman cs utoronto ca
Aaron Potechin
Ph. D. student
Mathematics Department
Massachusetts Institute of Technology
aaron potechin org
ABOUT THE AUTHORS
S IU M AN C HAN is a postdoc currently at Toronto, after spending one year at Princeton. He
completed his Ph. D. at Berkeley under Luca Trevisan and Elchanan Mossel. He did
his M. S. at Toronto under Toniann Pitassi, and his undergrad at the Chinese University
of Hong Kong under Leizhen Cai. He is interested in lower bounds in computational
complexity, like his clone Siu On. Siu Man is currently occupied with space and
parallel complexity, and more generally with the understanding of proofs, algorithms,
and complexity in different mathematical models via combinatorics. He procrastinates
by dreaming of upgrading his camera gears and buying more lenses.
A ARON P OTECHIN did his undergraduate studies at Princeton, which was followed by Part III
of the Mathematical Tripos at Cambridge. He is now a graduate student at MIT working
under Jonathan Kelner. While he is interested in a wide variety of topics, his primary
research focus for the past few years has been on trying to prove space lower bounds
using the switching network model. At FOCS 2010 he received the Machtey Award
for the Best Student Paper for his paper “Bounds on Monotone Switching Networks for
Directed Connectivity.”
T HEORY OF C OMPUTING, Volume 10 (15), 2014, pp. 389–419 419