\( \def\<#1>{\left<#1\right>} \newcommand{\CC}{\mathbf{C}} \)

What have read-once branching programs to do with $NL/\mathrm{poly}$?

Recall that $NL/\mathrm{poly}$ is the class of all boolean functions of $n$ variables that can be computed by (unrestricted) nondeterministic branching programs (NBPs) of polynomial in $n$ size. We are far from being able to prove strong lower bounds for NBPs: the highest remains a lower bound $\Omega(n^{3/2}/\log n)$ proved by Nechiporuk 45 years ago. Exponential lower bounds were only proved for 1-NBPs (read-once NBPs), where along every path (be it consistent or not), no variable is tested more than once. So, we already can exhibit explicit boolean functions lying outside the class 1-$NL/\mathrm{poly}$ of all boolean functions computable by 1-NBPs of polynomial size (see e.g. Sect. 16.3 in the book). Unfortunately, we can show this only for some functions with specific properties. Should we try to find new arguments allowing us to prove strong lower bounds for other functions is this (so weak) model?

A positive answer was recently given by Robert Myers and Henning Urbat [1]. They observed that, at least in principle, one could prove $f\not\in NL/\mathrm{poly}$ by proving superpolynomial lower bounds on the size of 1-NBPs computing the so-called "powers" $f^d$ of $f$:

Theorem (Myers-Urbat [1]):
$f\in NL/\mathrm{poly}$ if and only if $f^d\in \mbox{1-}NL/\mathrm{poly}$ for some $d=\mathrm{poly}(n)$.

Recall that a nondeterministic branching program (NBP) for a boolean function $f(y_1,\ldots,y_n)$ is a directed acyclic graph some of whose wires are labeled by tests $y_i=0$ or $y_i=1$. An input vector is accepted iff there is an st-path, all tests along which are consistent with the corresponding bits of that vector. To keep things simple, we will assume that all wires have labels, and that the underlying graph is layered, that is, the nodes are partitioned into a number of layers, and wires go only from nodes in one layer to nodes in the next. By a 1-NBP we will understand an NBP which is syntactically read-once, i.e. in which along every path, no variable is tested more than once. The depth of an NBP is the length of a longest st-path in it. Note that the depth of a 1-NBP never exceeds the number of variables. By the size of an NBP we will mean the number of its wires (edges).

Let $d$ be a positive integer. The $d$-th power $y^d$ of a vector $y\in\{0,1\}^n$ is a vector $x=yy\cdots y$ in $\{0,1\}^{dn}$ consisting of $d$ copies of $y$. The $d$-th power of a boolean function $f:\{0,1\}^n\to\{0,1\}$ is a boolean function $f^d:\{0,1\}^{dn}\to\{0,1\}$ defined as follows: \[ f^d(x)=\begin{cases} 1 & \mbox{if $x\neq y^d$ for any $y\in\{0,1\}^n$}\tag{*}\\ f(y) & \mbox{if $x=y^d$} \end{cases} \] Since no vector $x$ can be a $d$-th power of two distinct vectors $y\neq y'$, the function $f^d(x)$ is well-defined. A boolean function $g:\{0,1\}^{dn}\to\{0,1\}$ approximates the $d$-th power of $f$, if $g(x)=f^d(x)$ ($=f(y)$) for all $x=y^d$; on non-powers $x$, $g$ can take arbitrary values $0$ or $1$. Say that two branching programs are equivalent if their underlying graphs are the same (that is, only the test made at the wires may differ).

Lemma 1:
For every NBP of depth $d$ computing a boolean function $f$, there is an equivalent 1-NBP approximating $f^d$.
Proof: Let $P(y)$ be an NBP of size $S$ computing $f(y)$, and $d$ be its depth. The program may be not read-once: along a path, the same variable $y_i$ may be tested several times. Since our program is layered, this means that $y_i$ may occur as a label in several layers. To obtain a read-once program, we just replace each occurrence of $y_i$ in the $k$-th layer by a $k$-th copy of $y_i$. That is, for each variable $y_i$, we take $d$ its new copies $x_{i,1},x_{i,2},\ldots,x_{i,d}$. If a test $y_i=b$ with $b\in \{0,1\}$ is made at a wire on the $k$-th layer, then replace this test by $x_{i,k}=b$. Let $P'(x)$ be the resulting read-once NBP on the new variables.

It is easy to see that, if $x=y^d$ is a power of $y$, then $P'(x)=P(y)$ ($=f(y)$). Indeed, if $P(y)=1$ then there is an st-path in $P$ along which all tests $y_i=b$ are consistent with the actual bits of $y$. Since $x_{i,1}=x_{i,2}=\ldots=x_{i,d}=y_i$, the corresponding path $p'$ in $P'$ is also consistent with $x$. By the same reason, input $x$ is be rejected by $P'$ if $y$ was rejected by $P$. $\Box$

We can easily modify the obtained 1-NBP to an oblivious 1-NBP computing (not just approximating) $f^d$.

Lemma 2:
If a boolean function $f$ of $n$ variables can be computed by a layered NBP of size $S$ and depth $d$, then the $d$-th power $f^d$ of $f$ can be computed by an oblivious $1$-NBP of size at most a constant times $nS+n^2d^3$ and depth $dn$.
Proof: To make the 1-NBP from Lemma 1 oblivious, we can just "stretch" it out by adding "dummy" tests accepting everything, i.e. parallel wires with two tests $x_{i,k}=0$ and $x_{i,k}=1$. That is, we replace a wire on the $k$-th layer of $P'$ making a test $x_{i,k}=b$ by a sequence of $n$ wires, the $i$-th of which makes the test $x_{i,k}=b$, and the remaining wires make in parallel both tests $x_{j,k}=0$ and $x_{j,k}=1$, for $j\neq i$: \[\displaystyle \bullet\xrightarrow{x_{i,k}=b}\bullet\ \ \ \mbox{in the $k$-th layer of $P'(x)$ is replaced by }\ \ \bullet \xrightarrow[x_{1,k}=0]{x_{1,k}=1} \circ \xrightarrow[x_{2,k}=0]{x_{2,k}=1} \cdots \circ \xrightarrow[x_{i-1,k}=0]{x_{i-1,k}=1} \circ \xrightarrow[\Uparrow]{x_{i,k}=b} \circ \xrightarrow[x_{i+1,k}=0]{x_{i+1,k}=1} \cdots \circ \xrightarrow[x_{n,k}=0]{x_{n,k}=1} \bullet \] If $P'$ had size $S$ and depth $d$, then the obtained 1-NBP $P''$ is oblivious, approximates $f^d$, has size $O(nS)$ and depth $dn$. Along each st-path in $P''$, the variables are tested in one and the same order $x_{1,1},x_{2,1},\ldots,x_{n,1}, x_{1,2},x_{2,2},x_{3,2},\ldots$.

We can easily modify $P''$ to an oblivious 1-NBP computing (not just approximating) $f^d$, just by adding in parallel an oblivious 1-NBP $Q(x)$ such that $Q(x)=1$ iff $x$ is not a $d$-th power. This last event happens iff there is an $i\in\{1,\ldots,n\}$ and $k=l\mod{n}$ such that $x_{i,k}=0$ and $x_{i,l}=1$, or $x_{i,k}=1$ and $x_{i,l}=0$. For each fixed triple $(i,k,l)$, this can be tested by a simple 1-NBP of constant size, and hence, by oblivious 1-NBP of size $O(dn)$. By taking $n\tbinom{d}{2}$ disjoint copies of these oblivious 1-NBP's, we obtain an oblivious 1-NBP $Q(x)$ of size $O(n^2d^3)$ which accepts a string $x$ iff $x$ is not a $d$-th power. $\Box$

Let 1-$\mathrm{NBP}$ denote the class of all boolean functions $f(y)$ of $n$ variables for which there is a $d=poly(n)$ such that the $d$-th power $f^d(x)$ of $f(y)$ has an oblivious 1-NBP of size polynomial in $dn$ (and hence, also in $n$).

Corollary: $NL/\mathrm{poly} \subseteq $ 1-$\mathrm{NBP}$.
In fact, using the well-known result of Immerman and Szelepcsenyi that $NL/\mathrm{poly}$ is closed under negations (complements), it is shown in [1] that the equality holds.

Examples

Example 1: To illustrate how an NBP is made oblivious, consider the NBP $P(y_1,y_2)$ of depth 3 (consisting of just one path): \[ \bullet\xrightarrow{y_1=1} \bullet\xrightarrow{y_1=1} \bullet\xrightarrow{y_2=0} \bullet\rightarrow\ \mbox{accept} \] which computes $f:\{0,1\}^2\to\{0,1\}$ defined by $f(y) = 1$ iff $y = 10$. We then replace each edge by $n=2$ suitable edges, and relabel the variables to $x_{1,1}, x_{2,1}, x_{1,2}, x_{2,2}, x_{1,3}, x_{2,3}$ in order; here $x_{1,1}, x_{1,2}, x_{1,3}$ are $d=3$ copies of $y_1$, and $x_{2,1}, x_{2,2}, x_{2,3}$ are $d=3$ copies of $y_2$: \[ \bullet\xrightarrow[\Uparrow]{x_{1,1}=1} \circ\xrightarrow[x_{2,1}=0]{x_{2,1}=1} \bullet\xrightarrow[\Uparrow]{x_{1,2}=1} \circ\xrightarrow[x_{2,2}=0]{x_{2,2}=1} \bullet\xrightarrow[x_{1,3}=0]{x_{1,3}=1} \circ\xrightarrow[\Uparrow]{x_{2,3}=0} \bullet\rightarrow\ \mbox{accept} \] The above NBP $P'$ computes a boolean function $f^3: \{0,1\}^6 \to\{0,1\}$. Importantly, if $x = y^3$ then $f^3(x) = 1$ iff $x_{1,1}=x_{1,2}=x_{1,3}=1$, and $x_{2,1}=x_{2,2}=x_{2,3}=0$. Then $f^3(y^3) = 1$ iff $f(y) = 1$.

Example 2: The main hitch when dealing with general NBPs is the presence of "null-paths" along which contradictory tests $y_i=0$ and $y_i=1$ on the same variable $y_i$ are made. These paths contribute nothing (they do not accept anything), but it is known that their presence may exponentially reduce the program size (see Prop 16.13 in the book). So, what happens with null-paths when going from NBP $P$ to 1-NBP $P'$? To see this, consider such a path: \[ \bullet\xrightarrow{y_1=1} \bullet\xrightarrow{y_1=0} \bullet\xrightarrow{y_2=0} \bullet\rightarrow\ \mbox{accept} \] In the corresponding (non-oblivious) 1-NBP we will get: \[ \bullet\xrightarrow[\Uparrow]{x_{1,1}=1} \bullet\xrightarrow[\Uparrow]{x_{1,2}=0} \bullet\xrightarrow{x_{2,3}=0} \bullet\rightarrow\ \mbox{accept} \] This path accepts no powers $y^3=ababab$ with $a,b\in\{0,1\}^2$, because only vectors of the form $1\ast 0\ast \ast 0$ may be consistent with this path.

This explains what happens with null-paths: they are just turned into "accepting non-powers" paths.

Notes

  1. In the definition (*) of the $d$-th power $f^d$, it was important that $f^d$ must accept all non-powers. Had we replaced "accept" by "reject", then exponential lower bounds for 1-NBPs computing $f^d$ would be easy to prove! Such a bound would hold for any polynomial power $f^d$ of, say, $f$ = the Exact Perfect Matching function (see Sect. 16.3 in the book).

  2. So, why we still haven't proved $f\not\in NL/\mathrm{poly}$? Just because the existing lower bounds arguments for 1-NBPs work only for boolean functions that are "isolated enough": if $f(x)=1$ then $f(x')=0$ for all vectors obtained from $x$ by flipping up to some fixed number of bits (see, e.g. Thm. 16.9 in the book). The proof is then just a cut-and-paste argument. Note, however, that $f^d$ is highly non-isolated: if $x=y^d$ is a power then, independent of what the actual value $f(y)$ is, we have $f^d(x')=1$ for all vectors $x'\neq x$ of hamming distance $\leq d$ from $x$. If, say, all vectors in $f^{-1}(1)$ have the same number of ones (lie in the same slice of the binary $n$-cube), then in the $dn$-cube, the corresponding slice of $f^d$ will be surrounded by a wide strip of accepted vectors:
    powering
    For functions of such a form, the simple cut-and-paste argument in their 1-NBPs does not seem to work.

  3. So far, no exponential lower bounds are known for (general) NBPs even of depth $n$ = number of variables. To have such a lower bound for function $f$ of $n$ variables, we need to show that $f^d$ requires exponential 1-NBPs for $d=n$.

  4. The transition "general NBP $\mapsto$ read-once NBP" is reminiscent of what happens in graph complexity. Having a boolean function $f(y_1,\ldots,y_{m})$, the idea of graph complexity is to introduce $n=2^{m}$ new variables $x_u$, one for each vector $u\in\{0,1\}^m$. Then we replace an input literal $y_i^b$ in a (non-monotone) circuit for $f$ by an OR $\bigvee_{u\colon u_i=b}x_u$ of new variables. The obtained (monotone) circuit will then compute the adjacency function of the graph associated with $f$. In the case of branching programs, we just associate with each variable $y_i$ its $d$ copies $x_{i,1},x_{i,2},\ldots,x_{i,d}$, and the obtained 1-NBP will compute the $d$-th power $f^d$ of $f$.

  5. Actually, we can require that $f^d(x)=0$ for all non-powers $x$, if we move from read-once to read-twice NBPs. This can be done, for example, by adding a bunch of $2n$ paths making tests $x_{i,1}=x_{i,2}=\ldots=x_{i,d}$ for all $i=1,\ldots,n$. The obtained program is a syntactic read-$k$ NBP for $k=2$ (along each st-path, every variable is tested at most $k$ times). We already know how to prove exponential lower bounds for syntactic $k$-NBPs (Exercises 17.3-17-4 in the book): any dense boolean function without large rectangles requires large syntactic $k$-NBP. So, why we cannot use the rectangle method to prove lower bounds on read-2 times NBPs for $g(x):=f^d(x)$ with $g(x)=0$ for non-powers $x$? Good news is that $g$ cannot have larger rectangles than $f$. The problem, however, is that, even if the function $f$ is dense enough (accepts a constant fraction of all $2^n$ input vectors), its power $g$ is a very sparse subset of its domain $\{0,1\}^{dn}$, because $|g^{-1}(1)|=|f^{-1}(1)|\leq 2^n$.

    Reference:

    1. R. Myers and H. Urbat (2013): A Characterisation of NL/poly via Nondeterministic Finite Automata, in Proc. of 15th Workshop on Descriptional Complexity of Formal Systems (DCFS 2013, 22--25 July, 2013, London, Ontario, Canada), to appear. Manuscritpt
    S. Jukna, April 2013