A non-linear time lower bound for boolean branching programs

Abstract

We give an exponential lower bound for the size of any linear-time Boolean branching program computing an explicitly given function. More precisely, we prove that for all positive integers k and for all sufficiently small ε > 0, if n is sufficiently large then there is no Boolean (or 2-way) branching program of size less than 2εn which, for all inputs X ⊆{0,1,…,n−1}, computes in time kn the parity of the number of elements of theset of all pairs 〈x, y〉 with the property x ∈ X, y ∈ X, x < y, x + y ∈ X. For the proof of this fact we show that if A = (ai,j)mi=0,j=0 is a random n by n matrix over the field with 2 elements with the condition that “A is constant on each minor diagonal,” then with high probability the rank of each δ n by δ n submatrix of A is at least cδ | log δ |−2n, where c > 0 is an absolute constant and n is sufficiently large with respect to δ. (A preliminary version of this paper has appeared in the Proceedings of the 40th IEEE Symposium on Foundations of Computer Science.).