Volume 1 (2005) Article 8 pp. 149-176
A Non-linear Time Lower Bound for Boolean Branching Programs
Received: October 6, 2004
Revised: May 5, 2005
Published: October 5, 2005
Download article from ToC site:
[PDF (297K)]    [PS (486K)]    [PS.GZ (139K)]
[Source ZIP]
Keywords: complexity theory, lower bounds, space complexity, branching programs, Hankel matrices, matrix rigidity
ACM Classification: F.2.2, F.2.3
AMS Classification: 68Q17, 68Q15

Abstract: [Plain Text Version]

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.)