Lower bounds for branching programs of bounded repetition computing CNFs of bounded treewidth: an overview

VCLA will host a talk by Igor Razgon on Thursday, June 23, 2016.

ABSTRACT

In this talk I will overview my research towards understanding of complexity of branching programs with bounded repetition computing CNFs of bounded treewidth. In the first part of the talk I will briefly overview the result http://arxiv.org/abs/1411.0264 where we have shown that nondeterministic read-once branching programs (NROBPs) cannot efficiently (with FPT size) represent 2-CNFs of bounded treewidth. This result is implied by a combination of the following two statements: 1) The size of a NROBP computing a 2-CNF $varphi$ of a fixed degree is exponential in the *matching width* of the underlying graph of $varphi$. (The matching width is a parameter linearly related to pathwidth) 2) For each sufficiently large $k$, there is a class of graphs with degree at most $5$ and matching width about $k*log n$. A natural question for further research is whether this methodology can be extended to branching programs of a hgher repetition. In the second part of the talk I will show that essentially the same methodology allows to infer non-FPT lower bounds for so called $c$-OBDDs, a restricted variant of obvlivious read $c$-times branching programs where the order of variables being queried is obtained by concatenation of $c$ copies of a fixed permutation: http://arxiv.org/abs/1510.02951 Then I will show that matching width is unlikely to be useful for more general kinds of branching programs by demonstrating a CNF with a large matching width that can be efficiently represented by an oblivious read $2$-times branching program. In the last part of the talk, I will discuss a potential way to upgrade the above methodology is order to make it applicable for branching programs with a higher repretition. In particular, I will overview a new structural graph parameter represented in http://arxiv.org/abs/1510.05486 This parameter generalizes matching width. Moreover, we have shown that for a suitable transformation from a graph $G$ to a CNF $varphi$, the size of an (either monotone or oblivious) nondeterministic branching program computing $varphi$ is exponential in the size of this parameter for $G$. That is, the first step of the above two steps strategy has been accomplished for (monotone and obvlivious) non-deterministic branching programs with bounded repetition. However, the possibility of the second step remains open. In particular, we are not aware of a class of graphs for which this parameter is $O(log n)$ times greater than their treewidth. I will finish this talk by a formal statement of this open question along with explanation why it is of an independent interest from the graph theoretical perspective. The talk will be completely self-contained.