We give an exponential lower bound for the size of any linear-time Boolean branching program computing an explicitly given function. More precisely, we prove that for all positive integers $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,{\ldots},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 “$A$ is constant on each minor diagonal,” then with 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$.

(A preliminary version of this paper has appeared in the Proceedings of the 40th IEEE Symposium on Foundations of Computer Science.)