Theory of Computing
-------------------
Title : A Non-linear Time Lower Bound for Boolean Branching Programs
Authors : Miklos Ajtai
Volume : 1
Number : 8
Pages : 149-176
URL : https://theoryofcomputing.org/articles/v001a008
Abstract
--------
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
{0,1,...,n-1}, computes in time kn the parity of the number of
elements of the set of all pairs 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.)