__
TR99-026 | 7th July 1999 00:00
__

#### A Non-linear Time Lower Bound for Boolean Branching Programs

**Abstract:**
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$.