A lower bound for read-once-only branching programs

摘要

We give a Cn lower bound for read-once-only branching programs computing an explicit Boolean function. For n = (2ν, the function computes the parity of the number of triangles in a graph on ν vertices. This improves previous exp (c√n)) lower bounds for other graph functions by Wegener and Zák. The result implies a linear lower bound for the space complexity of this Boolean function on “eraser machines,” i.e., machines that erase each input bit immediately after having read it.