On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth
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 $\Omega(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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
On the read-once property of branching programs and CNFs of bounded treewidth
In this paper we prove a space lower bound of $n^{\Omega(k)}$ for non-deterministic (syntactic) read-once branching programs ({\sc nrobp}s) on functions expressible as {\sc cnf}s with treewidth at most $k$ of their prima…
NegationAn Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems
In this work, we revisit the problem of solving large-scale semidefinite programs using randomized first-order methods and stochastic smoothing. We introduce two oblivious stochastic mirror descent algorithms based on a …
Oblivious and Semi-Oblivious Boundedness for Existential Rules
We study the notion of boundedness in the context of positive existential rules, that is, whether there exists an upper bound to the depth of the chase procedure, that is independent from the initial instance. By focussi…
Bounded Memory Adversarial Bandits with Composite Anonymous Delayed Feedback
We study the adversarial bandit problem with composite anonymous delayed feedback. In this setting, losses of an action are split into $d$ components, spreading over consecutive rounds after the action is chosen. And in …
Branches of a Tree: Taking Derivatives of Programs with Discrete and Branching Randomness in High Energy Physics
We propose to apply several gradient estimation techniques to enable the differentiation of programs with discrete randomness in High Energy Physics. Such programs are common in High Energy Physics due to the presence of…
Clustering