Knowledge Compilation Meets Communication Complexity

1 Introduction

Finding suitable representation languages to encode information for reasoning is a basic issue of knowledge representation; the task typically involves striking a balance between competing requirements, for instance expressivity and tractability [Brachman and Levesque, 1984; Levesque and Brachman, 1987]. Since the complexity of reasoning algorithms is measured in terms of the size of the representation, a crucial aspect of this enterprise, and a central research topic in the area of knowledge compilation [Marquis, 2015], is the relative succinctness of representation languages [Gogic et al., 1995]. For instance, satisfiability of a Boolean function can be checked in linear time given its truth table, but we typically prefer encodings in terms of propositional formulas in spite of the increase in the complexity of satisfiability testing because these representations are exponentially more succinct.

In the propositional case, a systematic comparison of fully expressive, tractable representation languages was carried out by Darwiche and Marquis [2002]. One of the main aims of their work was to determine the relative succinctness of languages and decide whether representations in one language can be translated into another language at the cost of increasing the representation size at most polynomially. Showing unconditionally that such a transformation does not exist typically involves two parts: first, giving an upper bound on the representation size of a carefully chosen function f in the first language; and second, proving a non-trivial lower bound on the representation size of f in the second language. The latter part tends to become increasingly difficult with the succinctness of the representation language.

Many of the languages considered in knowledge compilation are sub-classes of the class of circuits in decomposable negation normal form, or DNNFs [Darwiche, 2001]. The limitations of DNNFs are generally not well understood, as witnessed by the lack of general techniques for proving strong lower bounds on the size of DNNF representations.

Indeed, lower bounds on the size of DNNF representations can be proved by lifting lower bounds on nondeterministic read-once branching programs using a quasipolynomial simulation of DNNFs by nondeterministic read-once branching programs [Razgon, 2015; Beame and Liew, 2015], or by leveraging lower bounds from monotone circuit complexity [Bova et al., 2014], but these approaches only lead to "weakly exponential" lower bounds of the form exp(n⌦(1) ) and do not provide a fine-grained understanding of the complexity of DNNFs. "Strongly exponential" lower bounds of the form exp(⌦(n)) have been obtained using a more direct approach, but at the cost of fairly involved combinatorial arguments that are particular to the class of functions against which lower bounds are shown [Ponnuswami and Venkateswaran, 2004; Bova et al., 2014].

In this paper, we introduce a general approach to proving lower bounds for DNNFs by establishing a connection between the DNNF size and the multi-partition communication complexity of Boolean functions [Duris et al., 2004]. This connection allows us to translate lower bounds on the communication complexity into lower bounds on the DNNF and deterministic DNNF (d-DNNF) size [Darwiche, 2001b]. Using this technique, we gain new insights into the limits of DNNFs and d-DNNFs. In particular, we prove exponential separations of DNNFs from d-DNNFs and of CNF formulas (even in prime implicates normal form) fromDNNFs.

In a nutshell, the communication complexity of a function f : X⇥Y !Z is the number of bits two individuals (usually named Alice and Bob) have to exchange to compute f(x↪ y) if one only knows x and the other only knows y. 1 To obtain lower bounds on this measure, communication complexity abstracts from the specifics of the communication process and takes a purely combinatorial view, the fundamental notion of which is that of a (combinatorial) rectangle. Formally, a rectangle in X ⇥Y is a subset R ✓ X ⇥Y such that R = A⇥B for some A ✓ X and B ✓ Y . The communication complexity of a function f yields an upper bound on the size of a partition of the input space into rectangles on which f assumes the same value. Accordingly, lower bounds on the number of rectangles in such a partition provide lower bounds on the communication complexity, and researchers have developed powerful tools to prove such bounds.

In turn, lower bounds on the communication complexity (or related measures) of a function can be used to derive lower bounds on the space required to compute this function in various models of computation: one argues that the communication complexity of a function f : D ! Z is high with respect to any (balanced) partition of D into X and Y , and then shows how an encoding of f in a particular representation language induces such a partition.

This is a standard technique for obtaining lower bounds on the representation size of (Boolean) functions as OBDDs (ordered binary decision diagrams) [Wegener, 2000]. Pipatsrisawat and Darwiche [2010] used a similar approach to prove lower bounds on the size of structured (deterministic) DNNFs, though without making the connection to communication complexity. Recently, Beame and Liew [2015] showed that the best-partition communication complexity of a function can be related to its sentential decision diagram (SDD) size, a subclass of DNNFs introduced by Darwiche [2011].

The model of communication complexity used in the above cases only considers a single partition of the input space into X and Y . To obtain lower bounds for DNNFs, we turn to a more flexible model that allows for multiple partitions [Duris et al., 2004]. We first prove that one needs at most one rectangle for each gate of a DNNF to cover its satisfying assignments. Here, it is useful to think of a DNNF in terms of its certificates. A certificate for a satisfying assignment is simply a minimal satisfied sub-DNNF that contains the output gate. Decomposability ensures that the certificates of a DNNF are trees, and certificates sharing a gate can be split and recombined into trees that are again certificates. It follows that the set of satisfying assignments with certificates that contain a particular gate is a rectangle (Theorem 1), and the union of these rectangles covers the satisfying assignments of the DNNF. In a d-DNNF, each satisfying assignment has exactly one certificate and the resulting rectangle cover is even disjoint.

In order to be able to transfer lower bounds from multipartition communication complexity, we have to refine the above construction and show that the set of satisfying assignments of a DNNF can be covered by a small number of rectangles with respect to balanced partitions, that is, partitions where each part contains a constant fraction of the input variables (Theorem 6).

1 For standard textbooks on the subject of communication complexity, see [Kushilevitz and Nisan, 1997; Hromkovic, 1997].

With this connection in place, we can translate lower bounds for the multi-partition communication complexity of a function into lower bounds for its DNNF size. Leveraging a result by Sauerhoff [2003], we get a lower bound of exp(⌦(n)) on the d-DNNF size of functions Sn (Theorem 8) whose DNNF size is polynomial in n (Proposition 7), thus separating DNNFs from d-DNNFs. Similarly, using a lower bound by Jukna and Schnitger [2002], we obtain a lower bound of exp(⌦(n2 )) on the DNNF size of functions JSn (Theorem 12) that can be represented by CNF formulas of size O(n2 ) (Proposition 11). This allows us to prove a separation of CNF formulas-in fact, even formulas in prime implicates normal form (PI)-from DNNFs, a result recently established in [Bova et al., 2014].

2 Preliminaries

In this section, we introduce the notions of decomposable circuits (from knowledge compilation) and rectangle covers (from communication complexity).

Decomposable NNFs (DNNFs). We consider circuits in negation normal form, in short NNFs, which are (Boolean) circuits over fanin 2 conjunction and disjunction gates, labelled with ^ and _, whose inputs are labeled by literals. 2 The size of an NNF C, denoted by ♣C♣, is the number of its gates. 3

For a gate g in an NNF C over X, we let Cg denote the subcircuit of C rooted at g. In particular, Cg = C if g is the output gate of C. For an NNF C over variables X and a gate g 2 C, we let var(Cg) ✓ X denote the variables appearing at input gates of Cg.

Let X be a finite set of variables. An NNF C over X is an NNF whose input gates are labelled with literals over variables in X. The (Boolean) function fC : ¶0↪ 1♦X ! ¶0↪ 1♦ computed by an NNF C over X is defined in the usual way. We let sat(C) = sat(fC) = f -1 C (1) denote the set of satisfying assignments of C and fC. Two NNFs C and C 0 over X are equivalent if sat(C) = sat(C 0 ); if C and C 0 are equivalent, we write C ⌘ C 0 . We also write C ⌘ f if fC = f .

2 For technical convenience we admit circuits formed by a single gate labelled with 0 or 1, but assume that circuits with at least two gates do not contain constants.

3 ♣C♣ > 0, as C contains at least the output gate. Circuits over unbounded fanin conjunctions and disjunctions can be quadratically simulated by fanin 2 circuits.

Let g be an ^-gate in an NNF C, and let h and h0 be two distinct gates wiring g in C. Then g is called decomposable if var(Ch) \ var(Ch0) = ;. An NNF whose ^-gates are decomposable is called a decomposable NNF (short, DNNF).

Let g be an _-gate in an NNF C, and let h and h0 be two distinct gates wiring g in C. Then g is called deterministic if sat(Ch) \ sat(Ch0 ) = ;, viewing each circuit involved in the equation as an NNF over var(C). An NNF whose _-gates are all deterministic is called a deterministic NNF.

Let Y be a finite nonempty set of variables. A variable tree (in short, a vtree) for the variable set Y is a rooted, full, ordered, binary tree T whose leaves correspond bijectively to Y ; for simplicity, we identify each leaf in T with the variable in Y it corresponds to.

For every internal node v of the vtree T, we let vl and vr denote respectively the left and right child of v. Moreover, we denote by Tv the subtree of T rooted at v. We also let Yv ✓ Y denote (the variables corresponding to) the leaves of Tv.

Let C be a DNNF over variables X, and let T be a vtree for the variable set Y . Let g be an ^-gate in C having wires from gates h and h0 . We say that g respects the node v of T if var(Ch) ✓ Yvl and var(Ch0 ) ✓ Yvr . We say that C respects the vtree T if each ^-gate in C respects some node in T . A DNNF C is called structured if it respects some vtree.

Rectangles and Covers. Let X be a finite set of variables. A partition of X is a sequence of pairwise disjoint subsets (blocks) of X whose union is X. A partition (X1↪X2) of X into two blocks is called balanced if ♣X♣◁3  min(♣X1♣↪ ♣X2♣); clearly, this is equivalent to max(♣X1♣↪ ♣X2♣)  2♣X♣◁3.

A (combinatorial) rectangle over X is a function r : ¶0↪ 1♦X ! ¶0↪ 1♦ such that there exist an underlying partition (X1↪ X2) of X and functions ri : ¶0↪ 1♦Xi ! ¶0↪ 1♦ for i = 1↪ 2 such that sat(r) = sat(r1 ) ⇥ sat(r2 ). A rectangle is called balanced if its underlying partition is balanced.

Let (X1↪X2) be a partition of X. For b1 : X1 ! ¶0↪ 1♦ and b2 : X2 ! ¶0↪ 1♦, we let b1 [ b2 : X1 [ X2 ! ¶0↪ 1♦ denote the assignment whose restriction to Xi equals bi for i = 1↪ 2. Also, for B1 ✓ ¶0↪ 1♦X1 and B2 ✓ ¶0↪ 1♦X2 , we let B1 ⇥B2 = ¶b1 [ b2 ♣ b1 2 B1↪ b2 2 B2♦.

We also call a subset R of ¶0↪ 1♦X a rectangle over X, with underlying partition (X1↪X2), if there exists a rectangle r : ¶0↪ 1♦X ! ¶0↪ 1♦, with underlying partition (X1↪X2), such that R = sat(r).

Let f : ¶0↪ 1♦X ! ¶0↪ 1♦ be a function. A finite set ¶ri♦ of rectangles over X is called a rectangle cover of f if

the rectangle cover is called disjoint if the union in (1) is disjoint. A rectangle cover is called balanced if each rectangle in the cover is balanced.

Note that, if f has a rectangle cover as in (1), thenf ⌘ Wi (C 1 i ^C 2 i ), where C 1 i (respectively, C 2 i ) is an NNF over the first (respectively, second) block of the partition underlying the ith rectangle in the cover; the outermost _-gate is deterministic if the cover is disjoint, and the ith ^-gate displayed is decomposable (by the partition of the ith rectangle).

3 Knowledge CompilationMeets Communication Complexity

In this section we show how to construct, given a (deterministic) DNNF C, a (disjoint) rectangle cover of size at most ♣C♣ for fC (Theorem 6), thus establishing a fundamental connection between knowledge compilation and communication complexity.

The construction is based on basic but crucial combinatorial properties of (deterministic) DNNFs, notably on the notion of certificate for a DNNF, and an operation eliminating gates in DNNFs, which we now define and study.

Let C be a DNNF on variables X. A certificate of C is a DNNF T on variables X such that: T contains the output gate of C; if T contains an ^-gate v of C, then T also contains every gate of C having an output wire to v; if T contains an _-gate v of C, then T also contains exactly one gate of C having an output wire to v. The output gate of T coincides with the output gate of C, and the gates of T inherit their labels and wires from C.

We let cert(C) denote the set of certificates of C. It is readily verified that

The following fact is an easy consequence of decomposability (and constant freeness).

Fact 1. Let C be a DNNF and let T 2 cert(C). The graph underlying T is a binary tree. Moreover, no two leaves of T are labeled by the same variable.

For a gate g of a DNNF C, we let cert(C↪ g) denote the set of certificates of C containing the gate g and let

in words, sat(C↪ g) contains those satisfying assignments of C that satisfy the subcircuit rooted at gate g.

The crucial combinatorial property of DNNFs is that sat(C↪ g) is a rectangle separating the variables in the subcircuit of C rooted at g. Formally,

Theorem 1. Let C be a DNNF on variables X and let g be a gate of C. Then sat(C↪ g) is a rectangle over X with underlying partition (var(Cg)↪ X ∩ var(Cg)).

In view of proving Theorem 1, we prepare the following.

Lemma 2. Let g be a gate of a DNNF C and let T 2 cert(C↪ g). Then

Proof of Lemma 2. Otherwise, let x be a variable contained in both var(T) ∩ var(Tg) and var(Cg). Then there exists a certificate T 0 2 cert(C↪ g) such that x 2 var(T 0g ). By Fact 1, T and T 0 are trees. By replacing Tg in T by T 0g , we obtain a certificate T of C where x occurs twice, contradicting Fact 1.

Proof of Theorem 1. Let Y = var(Cg) and Y 0 = X ∩ Y . Let b and b0 be in sat(C↪ g). It is sufficient to show that b♣Y [b0 ♣Y 0 is in sat(C↪ g), where b♣Y , denotes the restriction of b to Y and b0 ♣Y 0 denotes the restriction of b0 to Y 0 .

By Fact 1, T and T 0 are trees. By replacing T 0g in T 0 by Tg, we obtain a certificate S of C containing g, that is, S 2 cert(C↪ g). By the above observations, b♣Y [ b0 ♣Y 0 satisfies all literals in S, that is, b♣Y [ b0 ♣Y 0 is in sat(S). It follows by (3) that b♣Y [ b0 ♣Y 0 is in sat(C↪ g).

By (3), there exist certificates T and T 0 in cert(C↪ g) such that b 2 sat(T) and b0 2 sat(T 0 ). Then b satisfies all literals in Tg. Since var(Tg) ✓ Y , it follows that b♣Y satisfies all literals in Tg. Similarly, b0 satisfies all literals in T 0 ∩ T 0g ; and, by Lemma 2, it holds that var(T 0 ) ∩ var(T 0g ) ✓ Y 0 . Hence b0 ♣Y 0 satisfies all literals in T 0 ∩ T 0g .

As cert(C) = Sg2C cert(C↪ g), it trivially follows by (2) and (3) that

In words, C is covered by the rectangles induced by its gates (recall Theorem 1). However, in view of reusing known lower bounds on the size of rectangle covers (see Section 4), we need to find a subset of gates of C generating a balanced rectangle cover for C.

To this aim, we first introduce and study an operation on DNNFs that boils down to relabelling a noninput gate by 0 and propagating the information in the circuit.

Let C be a DNNF on variables X. We define an operation (0-propagation) that, given a DNNF C with some gates labelled with 0, returns either a single gate labelled with a 0 or a DNNF where no gates are labelled with 0. The operation iterates the following step until all 0s disappear (or the DNNF reduces to a single gate labelled 0). Let g be a gate in C labelled with 0. Then: delete all input wires of g; delete all output wires of g to _-gates; relabel all ^-gates wired by g and all fanin 0 _-gates by 0; delete all gates with no directed paths to the output gate.

Now we define the DNNF on variables X obtained by eliminating the noninput gate g in C, denoted by C - g, as the result of relabelling g by 0 and performing 0-propagation.

The impact of passing from C to C - g is dropping all certificates containing g in (2), as formalized by the following proposition (whose proof is omitted for space limitations).

Proposition 3. Let C be a DNNF and let g be a noninput gate of C. Then

The following lemma states a property of gate elimination crucial to our construction: in passing from C to C - g we only forget satisfying assignments in the rectangle sat(C↪ g).

Lemma 4. Let C be a DNNF and let g be a noninput gate of C. Then C - g is a DNNF and

Proof. Note that gate elimination preserves decomposability. The inclusions follow directly from Proposition 3, recalling (2) and (3).

In general, an assignment can satisfy more than one certificate. In this case, the left inclusion in Lemma 4 is strict. For instance, let D be a DNNF and let C = D _ D. Let g be the output gate of one copy of D in C. Then sat(C) = sat(D) and sat(C↪ g) = sat(D), so that sat(C) ∩ sat(C↪ g) = ;, but sat(C - g) = sat(D).

By contrast, the left inclusion in Lemma 4 becomes an equality in the deterministic case; in other words, eliminating a gate g in a deterministic DNNF C removes exactly the assignments in the rectangle sat(C↪ g). Formally,

Lemma 5. Let C be a deterministic DNNF and let g be a noninput gate of C. Then C - g is a deterministic DNNF and

Proof. We show that gate elimination preserves determinism. Assume that C - g contains a nondeterministic _-gate h, wired by gates k and k0 such that b 2 sat((C - g)k) and b 2 sat((C - g)k0). It follows by Proposition 3 that there exist certificates T and T 0 in cert(C) ∩ cert(C↪ g) such that b 2 sat(Tk) and b 2 sat(T 0k ). Then b 2 sat(Ck) and b 2 sat(Ck0), that is, h is nondeterministic in C, a contradiction.

For the equality, by Lemma 4 it suffices to prove that sat(C - g) is contained in sat(C) ∩ sat(C↪ g). Assume b 2 sat(C - g) so that, by Proposition 3, it holds that b 2 sat(T 0 ) for some T 0 2 cert(C) ∩ cert(C↪ g). In particular, b 2 sat(C). It suffices to show that b 62 sat(C↪ g).

Otherwise, by (3), b 2 sat(T) for some T 2 cert(C↪ g). Since T 0 62 cert(C↪ g), we have T 6= T 0 . It follows that there exist two distinct gates k and k0 in C, wiring an _-gate h in C, such that T contains k and T 0 contains k0 . Then b 2 sat(Tk) and b 2 sat(Tk0), so that b 2 sat(Ck) and b 2 sat(Ck0). Again, h is nondeterministic in C, a contradiction.

It follows from Lemma 4 that the process of iteratively eliminating gates in a DNNF (until it becomes unsatisfiable) yields a rectangle cover; moreover, by Lemma 5, the rectangle cover is disjoint if the DNNF is deterministic.

We strengthen the above remark by proving that a suitable elimination sequence in a (deterministic) DNNF C yields not just a (disjoint) rectangle cover of C, but indeed a balanced one, a crucial feature for the intended application (Section 4).

Theorem 6. Let C be a (deterministic) DNNF computing a function f. Then f has a balanced (disjoint) rectangle cover of size at most ♣C♣.

Proof. Let C = C 0 be a (deterministic) DNNF over variables X = var(C) computing f . For i = 0↪ 1↪ ▷ ▷ ▷, we find a suitable gate gi 2 C i and construct the (deterministic) DNNF C i+1 = C i -gi by eliminating gi in C i , until we hit l  ♣C♣ such that C l ⌘ 0. Along the way, we construct a set

that, we claim, is the desired rectangle cover of f.

For i = 0↪ 1↪ ▷ ▷ ▷, we choose the gate gi as follows. We distinguish two cases. If 2♣X♣◁3 < ♣var(C i )♣ then, by a descent from the output gate of C i , we find a gate gi 2 C i d-DNNF 6⇤⇤

6⇤

6⇤⇤ 6⇤⇤ ?

Table 1: Relative succinctness of knowledge compilation languages, taking into account the results of Section 4.1 (⇤ ) and Section 4.2 (⇤⇤ ).

such that ♣X♣◁3  ♣var(C igi )♣  2♣X♣◁3. By Theorem 1 we have that sat(C i ↪ gi) is a rectangle over X with underlying partition (var(C igi )↪ X ∩ var(C igi )). Then Ri = sat(C i ↪ gi) is a balanced rectangle over X.

If ♣var(C i )♣ < 2♣X♣◁3 then we let gi be the root of C i . We obtain the desired rectangle as follows. Let var(C i ) ✓ X0 ✓ X be obtained by adding to var(C i ) enough variables from X ∩ var(C i ) so that (X0 ↪ X ∩X0 ) is a balanced partition of X.

where we view C i as a DNNF over var(C i ). Then Ri is trivially a balanced rectangle over X.

It follows from the above construction and Lemma 4 that the set in (5) is a balanced rectangle cover of C. Moreover, if C is deterministic, then such rectangle cover is disjoint, because sat(C i ↪ gi) \ sat(C i+1 ) = ; by Lemma 5.

4 Separating Knowledge Representation Languages via Communication Complexity

In this section, we combine the connection between (deterministic) DNNFs and (disjoint) rectangle covers established in Section 3 with deep combinatorial lower bounds on the size of (disjoint) rectangle covers from the communication complexity literature to obtain exponential separations of DNNFs from deterministic DNNFs (Section 4.1) and of prime implicates (PI) from DNNFs (Section 4.2).

As illustrated in Table 1, these results allow us to answer several questions regarding the relative succinctness of languages left open in the "knowledge compilation map" (cf. Table 3 of [Darwiche and Marquis, 2002]).

4.1 DNNFs Versus Deterministic DNNFs

We first prove an exponential separation of DNNFs from deterministic DNNFs. The two classes are separated by a function introduced and studied by Sauerhoff [2003].

Let gn : ¶0↪ 1♦n ! ¶0↪ 1♦ be the function evaluating to 1 if and only if the sum of its inputs is divisible by 3. The Sauerhoff function Sn : ¶0↪ 1♦n2 ! ¶0↪ 1♦ is defined on the n ⇥ n matrix X = (xij )1i↪jn of variables by

where Rn↪ Cn : ¶0↪ 1♦n2 ! ¶0↪ 1♦ are defined by

and Cn(X) = Rn(X>), where X> denotes the transpose of X, and ⊕ denotes addition modulo 2.

The Sauerhoff function has polynomial DNNF size.

Proposition 7. Sn in (6) has DNNF size O(n2 ).

Proof (Sketch). The functions Rn and Cn have OBDDs of size O(n2 ), ordering the variables by rows and columns, respectively; their disjunction has size O(n2 ).

We use a highly nontrivial exponential lower bound on the size of balanced disjoint rectangle covers for Sn [Sauerhoff, 2003, Theorem 4.10].

Theorem 8 (Sauerhoff). Any balanced disjoint rectangle cover of the Sauerhoff function Sn in (6) has size 2⌦(n) .

We remark that Sauerhoff actually proves the above lower bound only for rectangles whose underlying partitions have blocks of the same size ◦1, but a careful inspection of the proof reveals that the same argument can be lifted to our more relaxed notion of balancedness.

By putting together Theorem 6 and Theorem 8, we get the following lower bound, which, in combination with Proposition 7, yields an explicit, unconditional, exponential separation of DNNFs from deterministic DNNFs:

Theorem 9. Sn in (6) has deterministic DNNF size 2⌦(n) .

4.2 Prime Implicates Versus DNNFs

Next, we show a (strongly) exponential separation of prime implicates (PIs) from DNNFs. In recent (unpublished) work [Bova et al., 2014], we established this separation by means of an involved combinatorial proof; here, we obtain the same result by leveraging a lower bound on the multi-partition communication complexity of a function studied by Jukna and Schnitger [2002], which is defined as follows.

For n ≥ 2, let Kn be the set of all 2-element subsets (edges) of ¶1↪ ▷ ▷ ▷ ↪ n♦. We view every subset of Kn as the edge set of a graph G whose vertex set is ¶1↪ ▷ ▷ ▷ ↪ n♦. We identify edges in Kn with Boolean variables, so that the graph G ✓ Kn is encoded by the ¶0↪ 1♦-assignment of Kn mapping a variable (edge) to 1 if and only if it is in the edge set of G.

A triangle T on n vertices is a graph with vertices ¶1↪ ▷ ▷ ▷ ↪ n♦ and edges ¶¶i↪ j♦↪ ¶i↪ k♦↪ ¶j↪ k♦♦, where ♣¶i↪ j↪ k♦♣ = 3; it corresponds to the assignment of Kn mapping ¶i↪ j♦, ¶i↪ k♦, ¶j↪ k♦ to 1 and the other edges to 0.

We let Tn be the set of all triangles on n vertices. For a set A ✓ Tn, we let

denote the function accepting exactly those graphs over ¶1↪ ▷ ▷ ▷ ↪ n♦ that avoid all triangles in A (the edge set of no triangle in A is contained in the edge set of the input graph).

Jukna and Schnitger [2002, Theorem 3.1] show an exponential lower bound on the size of balanced rectangle covers for functions as in (7).

Theorem 10 (Jukna and Schnitger). For every n there exists An ✓ Tn of size O(n2 ) such that any balanced rectangle cover of JSAn n in (7) has size 2⌦(n2 ) .

The Jukna-Schnitger function JSn : ¶0↪ 1♦Kn ! ¶0↪ 1♦ is defined by

where An is chosen by Theorem 10 (n ≥ 2).

It is readily verified that the Jukna-Schnitger function has polynomial PI size. Recall that a CNF F is in prime implicate (PI) form if every clause entailed by F is already entailed by a clause of F , and no clause of F entails another clause of F .

Proposition 11. JSn in (8) has PI size O(n2 ).

Proof (Sketch). Let JSn = JS An n . Take the CNF Fn stating that every triangle in An has an edge that is not in the input graph; it computes JSn and it is in PI. Also, Fn has size O(n2 ), since ♣An♣ = O(n2 ) by Theorem 10.

By combining Theorem 6 and Theorem 10, we obtain the following lower bound.

Jointly, Proposition 11 and Theorem 12 yield an unconditional, strongly exponential separation of PIs from DNNFs. As already observed in [Bova et al., 2014], since PI ✓ CNF ✓ NNF and d-DNNF ✓ DNNF, the remaining separations in Table 1 marked with follow from this result.

5 Structured Knowledge Representation Languages and Communication Complexity

The lower bound techniques for structured DNNFs introduced by Pipatsrisawat and Darwiche [2010] have a natural interpretation in terms of communication complexity. Their main result can be paraphrased thus:

Theorem 13 (Pipatsrisawat and Darwiche). Let D be a (deterministic) structured DNNF on variables X computing a function f and respecting a vtree T . For every node v 2 T , f has a (disjoint) rectangle cover of size at most ♣D♣ where each rectangle has underlying partition (Xv↪ X ∩ Xv).

Proof (Sketch). Let v be a node in T. We can find a gate g of D such that, for every certificate C of D containing g, it holds that var(Cg) ✓ Xv and var(C ∩Cg) ✓ X ∩Xv. We can show as in Theorem 1 that sat(D↪ g) is thus a rectangle with underlying partition (Xv↪ X ∩ Xv). We then apply a similar elimination process as in the proof of Theorem 6.

In contrast to Theorem 6, the above statement speaks about rectangle covers whose rectangles share the same underlying partition. Such covers are closely related to a measure known as the best-partition communication complexity [Lipton and Sedgewick, 1981], and Theorem 13 allows us to transfer lower bounds on the best-partition communication complexity and prove a conjecture by Pipatsrisawat and Darwiche [2010].

Let Xn = ¶x1↪ ▷ ▷ ▷ ↪ xn♦ and Yn = ¶y1↪ ▷ ▷ ▷ ↪ yn♦. Let T be a vtree for Xn [ Yn where the subtree rooted at the left (respectively, right) child of the root is a right-linear vtree for Xn (respectively, Yn). Pipatsrisawat and Darwiche [2010] conjecture that any deterministic DNNF computing

and respecting T has size exponential in n. We appeal to a nice piece of communication complexity theory to prove the following statement (thus confirming the conjecture).

Proposition 14. Let T be any vtree for Xn [ Yn containing a vtree for Xn as a subtree. Then any deterministic DNNF computing fn in (9) and respecting T has size at least 2n - 1.

A basic fact in communication complexity is that the rank of the communication matrix is a lower bound on the size of disjoint rectangle covers of a function [Jukna, 2012, Section 4.1].

Let f : ¶0↪ 1♦Z ! ¶0↪ 1♦ be a function, and let (Z1↪ Z2) be a partition of X where ♣Z1♣ = ♣Z2♣ = n. The communication matrix of f relative to (Z1↪ Z2), denoted by M(f↪ Z1↪ Z2) is a (Boolean) matrix whose rows and columns are indexed by assignments of Z1 and Z2, respectively, and whose (b1↪ b2)th entry equals f(b1 [ b2). 4

Theorem 15. Let (Z1↪ Z2) be a partition of the variables of a function f, where ♣Z1♣ = ♣Z2♣ = n. Then every disjoint rectangle cover of f into rectangles with underlying partition (Z1↪Z2) has size at least rank(M(f↪Z1↪Z2)).

The complement of the function fn in (9), called the disjointness function,

is a well studied object in communication complexity; we denote by Dn = M(dn↪ Xn↪ Yn) its communication matrix. The following fact is folklore [Jukna, 2012, Exercise 7.1].

Proposition 16. rank(Dn) = 2n .

Proof of Proposition 14. Let C be any deterministic DNNF computing fn in (9) and respecting a vtree T as in the hypothesis. By Theorem 13, fn has a disjoint rectangle cover of size at most ♣C♣ where each rectangle has underlying partition (Xn↪ Yn). Let En = M(fn↪ Xn↪ Yn). By Theorem 15, ♣C♣ ≥ rank(En). Since Dn = 1 - En by (10), we have 2n = rank(Dn) = rank(1 - En)  rank(1) + rank(En) = 1+rank(En) by Proposition 16 and basic linear algebra, hence rank(En) ≥ 2n - 1. We conclude that ♣C♣ ≥ 2n - 1.

We conclude by noting that the same general strategy used for obtaining the lower bounds in Section 4 works for structured DNNFs. For instance, the exponential lower bound on the structured DNNF size of the circular bit shift (CBS) function [Pipatsrisawat, 2010], follows directly by Theorem 13 and known exponential lower bounds on the size of rectangle covers for CBS in the best-partition model [Kushilevitz and Nisan, 1997, Chapter 7.2].

6 Conclusion

We established a connection between the DNNF size and the multi-partition communication complexity of Boolean functions. This connection allowed us to translate lower bounds from communication complexity into lower bounds on the (deterministic) DNNF size and prove exponential separations of DNNFs from d-DNNFs and of PIs from DNNFs.

We are confident that the applicability of our approach goes beyond the specific lower bound results proved here. In particular, we hope that it can help resolve a few questions from the "knowledge compilation map" that remain open [Darwiche and Marquis, 2002].

4 We regard communication matrices as matrices over the reals.

Acknowledgments

The first author was supported by the FWF Austrian Science Fund (P26200). The second author was supported by the French Agence Nationale de la Recherche, AGGREG project reference ANR-14-CE25-0017-01. The third author was supported by the ANR Blanc International ALCOCLAN. The fourth author was supported by the FWF Austrian Science Fund (P27721).