Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR99-026 | 7th July 1999 00:00

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

TR99-026
Authors: Miklos Ajtai
Publication: 8th July 1999 15:54
Keywords:

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

ISSN 1433-8092 | Imprint