# knowledge_compilation_meets_communication_complexity__c4689b65.pdf

Knowledge Compilation Meets Communication Complexity

Simone Bova

Florent Capelli Paris 7, IMJ-PRG

Stefan Mengel CNRS, CRIL UMR 8188

Friedrich Slivovsky

Choosing a language for knowledge representation and reasoning involves a trade-off between two competing desiderata: succinctness (the encoding should be small) and tractability (the language should support efﬁcient reasoning algorithms). The area of knowledge compilation is devoted to the systematic study of representation languages along these two dimensions in particular, it aims to determine the relative succinctness of languages. Showing that one language is more succinct than another typically involves proving a nontrivial lower bound on the encoding size of a carefully chosen function, and the corresponding arguments increase in difﬁculty with the succinctness of the target language. In this paper, we introduce a general technique for obtaining lower bounds on Decomposable Negation Normal Form (DNNFs), one of the most widely studied and succinct representation languages, by relating the size of DNNFs to multi-partition communication complexity. This allows us to directly translate lower bounds from the communication complexity literature into lower bounds on the size of DNNF representations. We use this approach to prove exponential separations of DNNFs from deterministic DNNFs and of CNF formulas from DNNFs.

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 mea-

sured 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, satisﬁability 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 satisﬁability 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: ﬁrst, giving an upper bound on the representation size of a carefully chosen function f in the ﬁrst 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 difﬁcult 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 ﬁne-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

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI-16)

separations of DNNFs from d-DNNFs and of CNF formulas (even in prime implicates normal form) from DNNFs.

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 speciﬁcs 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 ﬂexible model that allows for multiple partitions [Duris et al., 2004]. We ﬁrst 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 certiﬁcates. A certiﬁcate for a satisfying assignment is simply a minimal satisﬁed sub-DNNF that contains the output gate. Decomposability ensures that the certiﬁcates of a DNNF are trees, and certiﬁcates sharing a gate can be split and recombined into trees that are again certiﬁcates. It follows that the set of satisfying assignments with certiﬁcates 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 certiﬁcate and the resulting rectangle cover is even disjoint.

In order to be able to transfer lower bounds from multipartition communication complexity, we have to reﬁne the above construction and show that the set of satisfying as-

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

Figure 1: A DNNF (left) and a vtree (right). The DNNF is structured (it respects the vtree), but not deterministic.

signments 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).

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 JS n (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

Let X be a ﬁnite 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 f C : {0, 1}X ! {0, 1} computed by an NNF C over X is deﬁned in the usual way. We let sat(C) = sat(f C) = f 1

C (1) denote the set of satisfying assignments of C and f C. Two NNFs C and C0 over X are equivalent if sat(C) = sat(C0); if C and C0 are equivalent, we write C C0. We also write C f if f C = f.

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.

2For 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 ﬁnite 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 ﬁnite 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.

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}.

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.

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 ﬁnite set {ri} of rectangles over X is called a rectangle cover of f if

sat(ri); (1)

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 W

i (respectively, C2

i ) is an NNF over the ﬁrst (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 Compilation Meets 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 f C (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 certiﬁcate for a DNNF, and an operation eliminating gates in DNNFs, which we now deﬁne and study.

Let C be a DNNF on variables X. A certiﬁcate 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 certiﬁcates of C. It is readily veriﬁed that

sat(T). (2)

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 certiﬁcates of C containing the gate g and let

sat(C, g) =

T 2cert(C,g)

sat(T); (3)

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

var(T) \ var(Tg) var(C) \ var(Cg).

Proof of Lemma 2. Otherwise, let x be a variable contained in both var(T) \ var(Tg) and var(Cg). Then there exists a certiﬁcate T 0 2 cert(C, g) such that x 2 var(T 0

g). By Fact 1, T and T 0 are trees. By replacing Tg in T by T 0

g, we obtain a certiﬁcate 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 sufﬁcient 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 (3), there exist certiﬁcates T and T 0 in cert(C, g) such that b 2 sat(T) and b0 2 sat(T 0). Then b satisﬁes all literals in Tg. Since var(Tg) Y , it follows that b|Y satisﬁes all literals in Tg. Similarly, b0 satisﬁes all literals in T 0 \ T 0

g; and, by Lemma 2, it holds that var(T 0) \ var(T 0

g) Y 0. Hence b0|Y 0 satisﬁes all literals in T 0 \ T 0

g. By Fact 1, T and T 0 are trees. By replacing T 0

g in T 0 by Tg, we obtain a certiﬁcate S of C containing g, that is, S 2 cert(C, g). By the above observations, b|Y [ b0|Y 0 satisﬁes 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).

As cert(C) = S

g2C cert(C, g), it trivially follows by (2) and (3) that

sat(C, g). (4)

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 ﬁnd a subset of gates of C generating a balanced rectangle cover for C.

To this aim, we ﬁrst 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 deﬁne 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 deﬁne 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 certiﬁcates 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

T 2cert(C)\cert(C,g)

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

sat(C) \ sat(C, g) sat(C g) sat(C).

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 certiﬁcate. 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

sat(C) \ sat(C, g) = sat(C g).

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 certiﬁcates T and T 0 in cert(C) \ cert(C, g) such that b 2 sat(Tk) and b 2 sat(T 0

k). 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 sufﬁces 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 sufﬁces 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 unsatisﬁable) 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 = C0 be a (deterministic) DNNF over variables X = var(C) computing f. For i = 0, 1, . . ., we ﬁnd a suitable gate gi 2 Ci and construct the (deterministic) DNNF Ci+1 = Ci gi by eliminating gi in Ci, until we hit l |C| such that Cl 0. Along the way, we construct a set

{Ri | i = 0, . . . , l 1} (5)

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(Ci)| then, by a descent from the output gate of Ci, we ﬁnd a gate gi 2 Ci

NNF DNNF DNF CNF PI IP DNNF 6 6 6 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(Ci

gi)| 2|X|/3. By Theorem 1 we have that sat(Ci, gi) is a rectangle over X with underlying partition (var(Ci

gi), X \ var(Ci

gi)). Then Ri = sat(Ci, gi) is a balanced rectangle over X.

If |var(Ci)| < 2|X|/3 then we let gi be the root of Ci. We obtain the desired rectangle as follows. Let var(Ci) X0 X be obtained by adding to var(Ci) enough variables from X \ var(Ci) so that (X0, X \ X0) is a balanced partition of X. We put

Ri = (sat(Ci) {0, 1}X0\var(Ci)) {0, 1}X\X0, where we view Ci as a DNNF over var(Ci). 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(Ci, gi) \ sat(Ci+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 ﬁrst 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 deﬁned on the n n matrix X = (xij)1 i,j n of variables by

Sn(X) = Rn(X) _ Cn(X) (6)

where Rn, Cn : {0, 1}n2 ! {0, 1} are deﬁned by

gn(xi1, xi2, . . . , xin)

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 deﬁned 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

n : {0, 1}Kn ! {0, 1} (7)

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 JS n : {0, 1}Kn ! {0, 1} is deﬁned by

JS n = JS An

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

It is readily veriﬁed 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. JS n in (8) has PI size O(n2).

Proof (Sketch). Let JS n = 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 JS n 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.

Theorem 12. JS n in (8) has DNNF size 2 (n2).

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 ﬁnd a gate g of D such that, for every certiﬁcate 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

fn = (x1 y1) _ _ (xn yn) (9)

and respecting T has size exponential in n. We appeal to a nice piece of communication complexity theory to prove the following statement (thus conﬁrming 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.

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

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]. 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,

dn = fn = ( x1 _ y1) ( xn _ yn), (10)

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 conﬁdent that the applicability of our approach goes beyond the speciﬁc 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].

4We regard communication matrices as matrices over the reals.

Acknowledgments The ﬁrst 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).

References [Beame and Liew, 2015] P. Beame and V. Liew. New Lim-

its for Knowledge Compilation and Applications to Exact Model Counting. In In Proceedings of the 31st AAAI Conference on Conference on Uncertainty in Artiﬁcial Intelligence (UAI 2015), pages 131 140, 2015. [Bova et al., 2014] S. Bova, F. Capelli, S. Mengel, and

F. Slivovsky. A Strongly Exponential Separation of DNNFs from CNF Formulas. Co RR, abs/1411.1995, 2014. [Brachman and Levesque, 1984] R.J. Brachman and H.J.

Levesque. The Tractability of Subsumption in Frame-Based Description Languages. In Proceedings of the 4th AAAI Conference on Artiﬁcial Intelligence (AAAI 1984), pages 34 37, 2015. [Darwiche, 2001] A. Darwiche. Decomposable Negation Normal Form. J. ACM, 48(4):608 647, 2001. [Darwiche, 2001b] A. Darwiche. On the Tractable Counting

of Theory Models and its Application to Truth Maintenance and Belief Revision. J. Appl. Non-Classical Logics, 11(12):11 34, 2001. [Darwiche, 2011] A. Darwiche. SDD: A New Canonical Rep-

resentation of Propositional Knowledge Bases. In Proceedings of the 22nd International Joint Conference on Artiﬁcial Intelligence (IJCAI 2011), pages 819 826, 2011. [Darwiche and Marquis, 2002] A. Darwiche and P. Marquis.

A Knowledge Compilation Map. J. Artif. Intell. Res., 17:229 264, 2002. [Duris et al., 2004] P. Duris, J. Hromkovic, S. Jukna, M. Sauerhoff, and G. Schnitger. On Multi-Partition Communication Complexity. Inf. Comput., 194(1):49 75, 2004. [Gogic et al., 1995] G. Gogic, H.A. Kautz, C.H. Papadim-

itriou, and B. Selman. The Comparative Linguistics of Knowledge Representation. In Proceedings of the 14th International Joint Conference on Artiﬁcial Intelligence (IJCAI 1995), pages 862 869, 1995. [Hromkovic, 1997] J. Hromkovic. Communication Complex-

ity and Parallel Computing. Springer, 1997. [Jukna and Schnitger, 2002] S. Jukna and G. Schnitger.

Triangle-Freeness is Hard to Detect. Combinatorics, Probability & Computing, 11(6):549 569, 2002. [Jukna, 2012] S. Jukna. Boolean Function Complexity. Springer, 2012. [Kushilevitz and Nisan, 1997] E. Kushilevitz and N. Nisan.

Communication Complexity. Cambridge University Press, 1997.

[Levesque and Brachman, 1987] H.J. Levesque and R.J. Brachman. Expressiveness and Tractability in Knowledge Representation and Reasoning. Comput. Intell., 3:78 93, 1987. [Lipton and Sedgewick, 1981] R.J. Lipton and R. Sedgewick.

Lower Bounds for VLSI. In Proceedings of the 13th Annual ACM Symposium on Theory of Computing (STOC 1981),

pages 300 307, 1981. [Marquis, 2015] P. Marquis. Compile! In Proceedings of the 29th AAAI Conference on Artiﬁcial Intelligence (AAAI 2015), pages 4112 4118, 2015. [Pipatsrisawat and Darwiche, 2010] T. Pipatsrisawat and A. Darwiche. A Lower Bound on the Size of Decomposable Negation Normal Form. In Proceedings of the 24th AAAI Conference on Artiﬁcial Intelligence (AAAI 2010),

2010. [Pipatsrisawat, 2010] T. Pipatsrisawat. Reasoning with Propo-

sitional Knowledge: Frameworks for Boolean Satisﬁability and Knowledge Compilation. Ph D thesis, University of California Los Angeles, 2010. [Ponnuswami and Venkateswaran, 2004] A.K. Ponnuswami

and H. Venkateswaran. Monotone Multilinear Boolean Circuits for Bipartite Perfect Matching Require Exponential Size. In Proceedings of the 24th International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2004), pages 460 468, 2004. [Razgon, 2015] I. Razgon. Quasipolynomial Simulation of

DNNF by a Non-Deterministic Read-Once Branching Program. In Proceedings of the 21st International Conference on Principles and Practice of Constraint Programming (CP 2015), pages 367 375, 2015. [Sauerhoff, 2003] M. Sauerhoff. Approximation of Boolean

Functions by Combinatorial Rectangles. Theor. Comput. Sci., 1-3(301):45 78, 2003. [Wegener, 2000] I. Wegener. Branching Programs and Bi-

nary Decision Diagrams. SIAM, 2000.