Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR99-026 | 7th July 1999 00:00

A Non-linear Time Lower Bound for Boolean Branching Programs

RSS-Feed




TR99-026
Authors: Miklos Ajtai
Publication: 8th July 1999 15:54
Downloads: 2696
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