We prove that for all positive integer k and for all
sufficiently small \epsilon >0 if n is sufficiently large
then there is no Boolean (or 2-way) branching program of size
less than 2^{\epsilon n} which for all inputs
X\subseteq \lbrace 0,1,...,n-1\rbrace computes in time kn
the parity of the number of elements of the set of all pairs
\langle x,y\rangle with the property x\in X, y\in X ,
x<y, x+y\in X. For the proof of this fact we show that if
A=(a_{i,j})_{i=0,j=0}^{n} is a random n by n matrix over
the field with 2 elements with the condition that
``\forall i,j,k,l\in \lbrace 0,1,...,n-1\rbrace , i+j=k+l
implies a_{i,j}=a_{k,l}" then with a high probability the rank
of each \delta n by \delta n submatrix of A is at least
c\delta |\log \delta |^{-2}n, where c>0 is an absolute
constant and n is sufficiently large with respect to \delta.