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 primal graphs. This lower bound rules out the possibility of fixed-parameter space complexity of {\sc nrobp}s parameterized by $k$. We use lower bound for {\sc nrobp}s 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.
Code (0)
등록된 구현이 없습니다.
Tasks
NegationSimilar Papers 제목 키워드 기반
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 CNF…
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…
ClusteringLearning Pseudo-Backdoors for Mixed Integer Programs
We propose a machine learning approach for quickly solving Mixed Integer Programs (MIP) by learning to prioritize a set of decision variables, which we call pseudo-backdoors, for branching that results in faster solution…
Combinatorial OptimizationOT-Flow: Fast and Accurate Continuous Normalizing Flows via Optimal Transport
A normalizing flow is an invertible mapping between an arbitrary probability distribution and a standard normal distribution; it can be used for density estimation and statistical inference. Computing the flow follows th…
Density EstimationFinding Backdoors to Integer Programs: A Monte Carlo Tree Search Framework
In Mixed Integer Linear Programming (MIP), a (strong) backdoor is a "small" subset of an instance's integer variables with the following property: in a branch-and-bound procedure, the instance can be solved to global opt…