REVIEW 3 major objections 4 minor 16 references
Decision DNNFs with imbalanced conjunction cannot efficiently represent CNFs of bounded width
T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read Imbalanced Decision DNNFs cannot efficiently represent all CNFs of bounded primal treewidth; the hard family requires size $n^{\Omega((1-\alpha)\sqrt{k})}$.
desk verdict A genuinely new lower bound for Decision DNNFs with imbalanced gates, with a localized but repairable gap in the top-down case of the main combinatorial lemma. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central objects are $\wedge_d,\alpha$-fbdds: free binary decision diagrams (read-once branching programs) augmented with decomposable conjunction gates, where every conjunction gate is $\alpha$-imbalanced, meaning that at most one of its two children is large (depends on more than $n^\alpha$ variables). The hard formulas are $\varphi(T[h,k])$, edge CNFs of $T[h]\square P_k$, where $T[h]$ is a complete ternary tree of height $h$ and $P_k$ a path of $k$ vertices; these graphs have treewidth at most $2k-1$. The load-bearing combinatorial object is the target triple $(W, U_0, U_1)$: each connected component of $G[U_1]$ has size greater than $n^\alpha$; each vertex of $U_0$ is adjacent to both $U_1$ and $W$; $U_0$ is independent; the neighbours of $U_0$ inside $W$ are independent and private to each $U_0$-vertex. Lemma 8 asserts that every permutation of $V(T[h,k])$ admits a prefix $W$ and disjoint sets $U_0,U_1$ forming a target triple of rank $\Omega((1-\alpha)h\sqrt{k})$. The triple is converted into an independent set $I(P,U_0,U_1)$ of variables that every satisfying assignment carried through the designated BDD node must set to $1$, exactly the event whose probability is small enough for a union bound.
What would settle it
One concrete refutation would be a permutation of $V(T[h,k])$ in which every target triple has rank $o((1-\alpha)h\sqrt{k})$ for $h$ large relative to $k$, since Lemma 8 is necessary for the proof of Theorem 7. Alternatively, one can test the disputed induction step in Theorem 19: build a $(h_0,h_1)$-top-down permutation and a descendant subtree for which the stated hypotheses hold but the relevant prefix of that subtree contains fewer than $k$ vertices above height $h_0$, making Claim 3 unsupported.
Extended reading notes
Core claim
The central claim is Theorem 7: if $B$ is a $\wedge_d,\alpha$-fbdd computing $\varphi(T[h,k])$, then for $h$ sufficiently large compared with $k$, $|B| \ge n^{\Omega((1-\alpha)\sqrt{k})}$. Since the primal treewidth of $T[h,k]$ is at most $2k-1$ (Proposition 2), Theorem 1 follows as a corollary: an infinite class of CNFs of primal treewidth at most $k$ requires size $n^{\Omega((1-\alpha)\sqrt{k})}$ in this model. The hard instances are the edge formulas $\varphi(T[h,k])$, whose clauses are $(u\vee v)$ for the edges of the Cartesian product $T[h]\square P_k$ of a complete ternary tree of height $h$ with a path on $k$ vertices. The argument follows a 'mainstream path' in the BDD, a target path all of whose skipped alternatives are small; imbalance of the gates guarantees that such a path exists. Along that path, the combinatorial Lemma 8 produces a target triple whose large connected components are unfixed, so Lemma 5 forces them into the variable set of the final node, and Lemma 11 shows every satisfying assignment carried through that node assigns $1$ to an independent set of size $\Omega((1-\alpha)h\sqrt{k})$. A probability estimate and a union bound then force $n^{\Omega((1-\alpha)\sqrt{k})}$ distinct nodes. The abstract announces the stronger exponent $(1-\alpha)\cdot k$; the theorem statements and proof in the body establish the square-root form.
Load-bearing premise
The whole lower bound rests on the combinatorial engine Lemma 8, which says that every ordering of the vertices of $T[h,k]$ contains a prefix and two disjoint sets forming a target triple of rank $\Omega((1-\alpha)h\sqrt{k})$; as written, the proof of that lemma uses an induction hypothesis stronger than the one it states, so the engine is not fully verified.
Editorial extensions
If this is right
- For each large $k$, the constructed family $\Phi_k$ rules out fixed-parameter tractable representations: the required size grows as $n^{\Omega((1-\alpha)\sqrt{k})}$, so no $f(k)\cdot n^{O(1)}$ bound can hold uniformly for this model on these instances.
- The deterministic version of the open question is settled negatively, while general (non-deterministic) DNNF remains open; thus the boundary of FPT behaviour for bounded-treewidth CNFs lies inside the conjunction-splitting power of DNNFs.
- As a combinatorial corollary, every path decomposition of $T[h,k]$ has a bag of size $\Omega(\log n \cdot \sqrt{k})$ positioned so that all components of the corresponding suffix are larger than $n^\alpha$; this is the non-local width lower bound the paper proposes as a new form of bidimensionality.
- Because $|V(T[h,k])| = \Theta(3^h k)$ and the rank bound reads $h\sqrt{k}$, the construction is an XP, not ETH-style, lower bound: for each fixed $k$ the required size is polynomial with degree growing like $\sqrt{k}$.
Reading between the lines
- Editorial inference: the abstract promises exponent $(1-\alpha)k$, but the body proves only $(1-\alpha)\sqrt{k}$; closing that gap would require a stronger version of Lemma 8, with rank $\Omega((1-\alpha)hk)$ rather than $h\sqrt{k}$.
- Editorial inference: because the proof's cornerstone, that unfixed connected sets cannot be split by decomposable gates, fails for non-deterministic DNNFs, the same target-triple machinery will need a genuinely different probabilistic argument if the conjectured lower bound for general imbalanced DNNFs is to go through.
- Editorial inference: the target-triple construction transfers naturally to other graph products; testing it on grids or on $H$-minor-free families would show whether the $\sqrt{k}$ factor is an artifact of the tree-rooted structure or a general feature of the non-local width parameter.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies Decision DNNFs (modeled as ∧d-FBDDs) in which every conjunction gate is α-imbalanced, meaning at most one input of each gate depends on more than n^α variables. It asks whether CNFs of bounded primal treewidth admit FPT-size representations in this model, and answers this negatively in the deterministic setting: for each sufficiently large k it constructs an infinite class of CNFs of primal treewidth at most k whose ∧d,α-FBDD representations have size n^{Ω((1−α)√k)}. The hard instances are graph CNFs φ(T[h,k]) where T[h,k] is the Cartesian product of a complete ternary tree of height h with a path of length k. The proof combines a probabilistic union-bound argument over satisfying assignments with a new combinatorial statement, Lemma 8, which asserts that every permutation of V(T[h,k]) contains a prefix and two disjoint sets forming a 'target triple' of large rank. Lemma 8 is proved by a case analysis depending on whether the permutation is 'top-down' or 'bottom-up' with respect to two height parameters; the top-down case relies on an inductive statement (Theorem 19) about independent path sets, and the bottom-up case on a direct construction (Lemma 21). The paper also introduces a notion of non-local width and discusses potential connections to bidimensionality and to the non-deterministic DNNF case, which remains open.
Significance. If the proof gaps identified below are repaired, the result is a solid and interesting lower bound: it is, to my knowledge, the first separation showing that imbalanced decomposable conjunction gates do not retain the FPT representability of bounded-treewidth CNFs in the deterministic setting. The paper is largely self-contained, builds transparently on the prior FBDD lower-bound approach of [13], and introduces a genuinely new combinatorial notion (target triples and the associated non-local width) that may have independent use. The main technical work is original and does not fit parameters to the conclusion; the probabilistic argument and the graph-family construction are explicit and falsifiable. The open question for general (non-deterministic) DNNFs is honestly stated and the limitations of the current approach are discussed in the conclusion.
major comments (3)
- [Abstract; Theorems 1 and 7; Section 3] The abstract states a lower bound of n^{Ω((1−α)·k)} for the representation size, but Theorem 1 and Theorem 7 state and prove only n^{Ω((1−α)√k)}. In the proof of Theorem 7 (Section 3), the probability bound uses |U0| ≥ Ω((1−α)·h√k) with h = Θ(log n), which yields n^{−Ω((1−α)√k)}, not n^{−Ω((1−α)k)}. The abstract and any summary statements must be corrected to the √k exponent unless the stronger bound is proved.
- [Section 4, Theorem 19, Claim 3] The induction step of Theorem 19 applies the induction hypothesis to t1,t2,t3 and then asserts in Claim 3 that |W0 ∩ π2 ∩ V_{>h0}(h,k,t)| ≥ k 'by assumption', because |W0 ∩ π1 ∩ V_{>h0}(h,k,t1)| ≥ k. However, the stated induction hypothesis guarantees only the existence of an independent path set and a disjoint S ∈ S_{h0}(h,k,ti); it does not guarantee |πi ∩ V_{>h0}(h,k,ti)| ≥ k. Without this lower bound, Lemma 18 cannot be applied to U = π2, and the size lower bound in the top-down case of Lemma 8 does not follow. The fix is to add the condition |πi ∩ V_{>h0}(h,k,ti)| ≥ k to the inductive invariant; it is true in the base case by the definition of an (h0,h1)-td permutation and is preserved in the construction because V_{>h0}(h,k,t2) ⊆ V_{>h0}(h,k,t).
- [Section 4, Theorem 19 proof (parameter handling)] The proof of the induction step contains inconsistent notation that makes the argument unverifiable as written. The theorem statement requires an independent path set of size at least c(h1,height(t))√k, but the proof invokes the induction hypothesis with c(h0,height(ti)) and later states 'height(t2) = 4a' and '4(a+1) is exactly height(t)'. These assertions are false for the actual parameters h0,h1 (they ignore the contributions of h0 and h1). The intended calculation works if c is evaluated as c(h1,height(ti)) and the congruence condition is height(ti)−h1 ≡ 0 mod 4; with that reading, c(h1,height(t2)) + 1/65 = c(h1,height(t)). The same notational shift fixes the final reduction to a descendant t0, for which the equality c(h1,height(t0)) = c(h1,height(t)) is valid when height(t0) is the largest descendant height with height(t0)−h1 a multiple of 4 not exceeding height(t). This paragraph must be rewritten so that the parameter h1 is used consistently in the function c.
minor comments (4)
- [Sections 3.1 and 3.2] The references to 'Lemma 12' when applying the statement that S(φ)|g does not break a connected unfixed set should refer to Lemma 3 in Section 2; Lemma 12 as numbered states a different property.
- [Definition 14, item 2] The definition of Iu(P,U0,U1) in the second case reads 'Iu(P,U0,U1) = N(u) ∩ W = {u}'; this should be 'Iu(P,U0,U1) = {u}', since N(u) ∩ W is not generally equal to {u}.
- [Section 3, proof of Theorem 7] The line 'P r(Set(I(...))) ≤ 2^{|I|}' should involve the constant β from Claim 2 (or an equivalent constant absorbed into the exponent), and the subsequent bound 'n^{−Ω((1−α)·k)}' should read 'n^{−Ω((1−α)√k)}' to be consistent with the preceding h√k bound and with the theorem statement.
- [Throughout] There are several typos that should be corrected: 'number if variables' (Abstract), 'treewidht' (Introduction), 'collary' (Section 3), 'negaitvely' (Section 3.2), and 'hods' (Appendix).
Circularity Check
No significant circularity: the lower bound is built from a self-contained combinatorial engine (Lemma 8); the self-citations to [13] are non-load-bearing, and the flagged Theorem 19 induction gap is a repairable proof omission, not a circular reduction.
full rationale
The derivation chain is essentially self-contained; no claim reduces to a fitted input. Theorem 7's lower bound (|B| >= n^{Omega((1-alpha)sqrt(k))}) is assembled from (i) the combinatorial engine Lemma 8, proved in Section 4 via Theorem 19, Lemma 21, and Lemma 13; (ii) Lemma 9, converting Lemma 8's target triple into a mainstream-path triple via the rectangle Lemma 3 and Lemma 5; and (iii) a union bound over nodes u(g), with Pr(carried through u(g)) bounded by Lemma 11 and Claim 2. No proof step assumes its own conclusion. The imbalanced-gate definition (Definition 10) and the target-triple definition (Definition 13) use the same n^alpha threshold, but the rank bound Omega((1-alpha)h sqrt(k)) of Lemma 8 is established by induction on tree heights, not read off the definitions. The self-citation [13] supplies methodology ('an upgrade of an approach... [13]') and Claim 2, Pr(Set(S)) <= beta^{-|S|} for an independent set in a degree-6 graph; this claim is elementary and parameter-free, so it is independent support, not a circular load. The abstract's n^{Omega((1-alpha)k)} overstates the proven n^{Omega((1-alpha)sqrt(k))}; that is a strength error, not circularity. The one clear weakness is in Theorem 19's main step: Claim 3 asserts |W0 cap pi2 cap V_{>h0}(h,k,t)| >= k 'by assumption', while the stated induction hypothesis provides a prefix, an independent path set, and a disjoint S, but not the >=k intersection with V_{>h0}; the top-down case therefore uses an unstated strengthening. This is a proof gap (the base case obtains the property from the (h0,h1)-td definition), not a reduction of the theorem to its inputs. The Conclusion also honestly says the machinery fails for general DNNFs because non-determinism lets one assignment follow many paths, so Lemma 3 no longer applies. Score 1 reflects only the minor non-load-bearing self-citations.
Assumptions & free parameters
assumptions (5)
- domain assumption Decision DNNFs are equivalent to FBDDs equipped with decomposable conjunction nodes (∧d-fbdds).
- standard math For any independent set S in a graph of maximum degree 6, a random orientation of edges satisfies Pr(Set(S)) ≤ β^{−|S|} for some constant β>1.
- standard math The treewidth of T[h]□P_k is at most 2k−1.
- standard math The complete ternary tree satisfies 3^h < |V(T[h])| < 3^{h+1}.
- domain assumption α is a fixed constant with 0 < α < 1, and the imbalance threshold n^α is part of the model definition.
Cite this review
Pith. "Pith review of Decision DNNFs with imbalanced conjunction cannot efficiently represent CNFs of bounded width." pith.science (2026). https://pith.science/paper/KIUDM2ES
@misc{pith2026250516012,
author = {Pith},
title = {Pith review of: Decision DNNFs with imbalanced conjunction cannot efficiently represent CNFs of bounded width},
year = {2026},
howpublished = {\url{https://pith.science/paper/KIUDM2ES}},
note = {Machine review of arXiv:2505.16012}
}
abstract
Decomposable Negation Normal Forms \textsc{dnnf} [Darwiche, 'Decomposable Negation Normal Form', JACM, 2001] is a landmark Knowledge Compilation (\textsc{kc}) model, highly important both in \textsc{ai} and Theoretical Computer Science. Numerous restrictions of the model have been studied. In this paper we consider the restriction where all the gates are $\alpha$-imbalanced that is, at most one input of each gate depends on more than $n^{\alpha}$ variables (where $n$ is the number if variables of the function being represented). The concept of imbalanced gates has been first considered in [Lai, Liu, Yin 'New canonical representations by augmenting OBDDs with conjunctive decomposition', JAIR, 2017]. We consider the idea in the context of representation of \textsc{cnf}s of bounded primal treewidth. We pose an open question as to whether \textsc{cnf}s of bounded primal treewidth can be represented as \textsc{fpt}-sized \textsc{dnnf} with $\alpha$-imbalanced gates. We answer the question negatively for Decision \textsc{dnnf} with $\alpha$-imbalanced conjunction gates. In particular, we establish a lower bound of $n^{\Omega((1-\alpha) \cdot k)}$ for the representation size (where $k$ is the primal treewidth of the input \textsc{cnf}). The main engine for the above lower bound is a combinatorial result that may be of an independent interest in the area of parameterized complexity as it introduces a novel concept of bidimensionality.
Figures
Figures from the paper (4 more)
Reference graph
Works this paper leans on
-
[13]
On the read-once property of branching programs and cnfs of bounded treewidth
Igor Razgon. On the read-once property of branching programs and cnfs of bounded treewidth. Algorithmica, 75(2):277–294, 2016
work page 2016
-
[1]
Connecting knowledge compilation classes and width parameters
Antoine Amarilli, Florent Capelli, Mika¨ el Monet, and Pierre Senellart. Connecting knowledge compilation classes and width parameters. Theory Comput. Syst. , 64(5):861–914, 2020
work page 2020
-
[2]
Lower bounds for exact model counting and applications in probabilistic databases
Paul Beame, Jerry Li, Sudeepa Roy, and Dan Suciu. Lower bounds for exact model counting and applications in probabilistic databases. In Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence, Bellevue, WA, USA, August 11-15, 2013 , 2013
work page 2013
-
[3]
Expander cnfs have exponential DNNF size
Simone Bova, Florent Capelli, Stefan Mengel, and Friedrich Slivovsky. Expander cnfs have exponential DNNF size. CoRR, abs/1411.1995, 2014
arXiv 1995
-
[4]
Decomposable negation normal form
Adnan Darwiche. Decomposable negation normal form. J. ACM, 48(4):608– 647, 2001
work page 2001
-
[5]
SDD: A new canonical representation of propositional knowledge bases
Adnan Darwiche. SDD: A new canonical representation of propositional knowledge bases. In 22nd International Joint Conference on Artificial Intelligence (IJCAI) , pages 819–826, 2011
work page 2011
-
[6]
Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos. Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. ACM, 52(6):866–893, 2005
work page 2005
-
[7]
Graph Theory, 3d Edition , volume 173 of Graduate texts in
Reinhard Diestel. Graph Theory, 3d Edition , volume 173 of Graduate texts in. mathematics . Springer, 2005
work page 2005
Show all 16 references
-
[8]
Hypertree decompo- sitions and tractable queries
Georg Gottlob, Nicola Leone, and Francesco Scarcello. Hypertree decompo- sitions and tractable queries. J. Comput. Syst. Sci. , 64(3):579–627, 2002
2002
-
[9]
Generalized hy- pertree decompositions: NP-hardness and tractable variants
Georg Gottlob, Zolt´ an Mikl´ os, and Thomas Schwentick. Generalized hy- pertree decompositions: NP-hardness and tractable variants. J. ACM , 56(6):30:1–30:32, 2009. 28
2009
-
[10]
Lower bounds on dynamic programming for maximum weight independent set
Tuukka Korhonen. Lower bounds on dynamic programming for maximum weight independent set. In ICALP2021, volume 198 of LIPIcs, pages 87:1–87:14. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2021
2021
-
[11]
New canonical representations by augmenting obdds with conjunctive decomposition
Yong Lai, Dayou Liu, and Minghao Yin. New canonical representations by augmenting obdds with conjunctive decomposition. J. Artif. Intell. Res. , 58:453–521, 2017
2017
-
[12]
On compiling CNF into decision-dnnf
Umut Oztok and Adnan Darwiche. On compiling CNF into decision-dnnf. In Principles and Practice of Constraint Programming - 20th International Conference, (CP), pages 42–57, 2014
2014
-
[14]
On oblivious branching programs with bounded repetition that cannot efficiently compute cnfs of bounded treewidth
Igor Razgon. On oblivious branching programs with bounded repetition that cannot efficiently compute cnfs of bounded treewidth. Theory Comput. Syst., 61(3):755–776, 2017
2017
-
[15]
New width parameters of graphs
Martin Vatschelle. New width parameters of graphs. PhD thesis, Department of Informatics, University of Bergen, 2012. A Proof of Theorem 4. Let u be the source of B. Let u0 and u1 be the children of u. We assume w.l.o.g. that (u, u0) is an edge of P . In case u is labelled by ...
2012
-
[16]
Let a ∈ S(B)|{(x,0)}
Further on, assume that u is labelled with a variable x. Let a ∈ S(B)|{(x,0)}. By definition of S(B), a ∈ S(Bu0 ) × {0, 1}V0 where V0 = V ar(Bu1 ) \ V ar(Bu0 ) = ( V ar(B) \ {x}) \ V ar(Bu0 ) = V0(P ), the last equality holds since Alt(P ) = ∅. The converse also hods by defini...
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.