ECCC-Report TR99-026https://eccc.weizmann.ac.il/report/1999/026Comments and Revisions published for TR99-026en-usThu, 08 Jul 1999 15:54:02 +0300
Paper TR99-026
| A Non-linear Time Lower Bound for Boolean Branching Programs |
Miklos Ajtai
https://eccc.weizmann.ac.il/report/1999/026We 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$.
Thu, 08 Jul 1999 15:54:02 +0300https://eccc.weizmann.ac.il/report/1999/026