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 2n which for all inputs X01n?1 computes in time kn the parity of the number of elements of the set of all pairs xy with the property xX, yX, xy, x+yX. For the proof of this fact we show that if A=(aij)ni=0j=0 is a random n by n matrix over the field with 2 elements with the condition that ``ijkl01n?1 , i+j=k+l implies aij=akl" then with a high probability the rank of each n by n submatrix of A is at least clog?2n , where c0 is an absolute constant and n is sufficiently large with respect to .
展开▼
