Non-linear time lower bound for Boolean branching programs

Abstract

We prove that for all positive integer k and for all sufficiently small qq > 0 if n is sufficiently large then there is no Boolean (or 2-way) branching program of size less than 2 qqn which for all inputs X qq {0, 1, ..., n - 1} computes in time kn the parity of the number of elements of the set of all pairs 〈x,y〉 with the property x qq X, y qq X, x < y, x + y qq X. For the proof of this fact we show that if A = (a i,j) i=0,j=0n is a random n by n matrix over the field with 2 elements with the condition that 'qqi, j, k, l qq {0, 1, ..., n - 1}, i + j = k + l implies a i,j = a k,l' then with a 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 δ.