On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth
This addresses a theoretical problem in computational complexity for researchers studying branching programs and CNF representations, providing new lower bounds and separations, but it is incremental as it builds on existing models like OBDDs.
The paper tackles the complexity of computing CNFs of bounded treewidth using an extension of ordered binary decision diagrams called c-OBDDs, showing that for each k≥3, there exists a class of CNFs with treewidth k requiring c-OBDDs of size Ω(n^{k/(8c-4)}), and uses this to separate c-OBDDs from sentential decision diagrams.
In this paper we study complexity of an extension of ordered binary decision diagrams (OBDDs) called $c$-OBDDs on CNFs of bounded (primal graph) treewidth. In particular, we show that for each $k$ there is a class of CNFs of treewidth $k \geq 3$ for which the equivalent $c$-OBDDs are of size $Ω(n^{k/(8c-4)})$. Moreover, this lower bound holds if $c$-OBDD is non-deterministic and semantic. Our second result uses the above lower bound to separate the above model from sentential decision diagrams (SDDs). In order to obtain the lower bound, we use a structural graph parameter called matching width. Our third result shows that matching width and pathwidth are linearly related.