We prove that for all positive integer k and for all sufficiently small \math if n is sufficiently large then there is no Boolean (or 2-way) branching program of size less than \math which for all inputs \math computes in time kn the parity of the number of elements of the set of all pairs x,y with the property \math. For the proof of this fact we show that if \mathn is a random n by n matrix over the field with 2 elements with the condition that "\math, \math implies \math" then with a high probability the rank of each \math by \math submatrix of A is at least \math, where \math is an absolute constant and n is sufficiently large with respect to \math.