A non-linear time lower bound for Boolean branching programs

We prove that for all positive integer 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^em which for all inputs X⊆{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∈X, y∈X, x<y, x+y∈X. For the proof of this fact we show that if A=(α_i,j)_{i=0, j=0}ⁿ is a random n by n matrix over the field with 2 elements with the condition that “∀, j, k, l∈{0, 1, ..., n-1}, i+j=k+l implies α_i,j=α_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 δ