# On the read-once property of branching programs and CNFs of bounded treewidth

arXiv: https://arxiv.org/abs/1411.0264 · HTML: https://mlsanity.com/paper/1411.0264/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Nov 2014.

## Built on by (most cited first, 1 of 1)

- [Pseudo Polynomial-Time Top-k Algorithms for d-DNNF Circuits](https://mlsanity.com/paper/2202.05938/) (2022)

## Abstract (arXiv)

In this paper we prove a space lower bound of nOmega(k) for non-deterministic (syntactic) read-once branching programs (sc nrobps) on functions expressible as sc cnfs with treewidth at most k of their primal graphs. This lower bound rules out the possibility of fixed-parameter space complexity of sc nrobps parameterized by k. We use lower bound for sc nrobps to obtain a quasi-polynomial separation between Free Binary Decision Diagrams and Decision Decomposable Negation Normal Forms, essentially matching the existing upper bound introduced by Beame et al. and thus proving the tightness of the latter.