A lower bound for read-once-only branching programs (Q1107323)

The authors present an exponential lower bound for read-once-only branching programs computing an explicit function. The function is defined as follows. For any natural number v, binary strings of length \(n=\left( \begin{matrix} v\\ 2\end{matrix} \right)\) represent graphs with v vertices. Each position in such a string corresponds to a pair of vertices and 0 or 1 on the position encodes the absence or presence, respectively, of an edge between the vertices. G(x) denotes the graph encoded by a string x. Let \(f(x)=number\) of triangles in G(x) (mod 2). The main result of the paper then reads as follows: There exists a positive constant c such that every read-once-only branching program computing \(f_ n\) has size at least \(2^{c\cdot n}.\) The result implies a linear lower bound for the eraser RAM space complexity of the above defined Boolean function. Eraser RAM can specify the order in which the symbols from the input are read, but once an input square has been read, it is erased.