On lower bounds for read-\(k\)-times branching programs (Q2366719): Difference between revisions

Proving nontrivial lower bounds for read-\(k\)-times switching networks (called also, nondeterministic branching programs) is a long standing problem. Such bounds were obtained only for oblivious read-\(k\)-times schemes. The authors consider another restriction: they require that no variable occurs more than \(k\) times on any path (whether or not consistent). An explicit Boolean function is exhibited which requires such ``syntactic'' read-\(k\)-times contact schemes of size \(\exp\left(\Omega\left({n\over 4^ kk^ 3}\right)\right)\). The proof is based on the following combinatorial result concerning Sylvester matrices, i.e. \(n\times n\) matrices \(A=\{a_{S,T}\}\) over \(GF(3)\) with rows and columns indexed by the subsets \(T,S\subseteq\{1,2,\dots,\log n\}\) and entries \(a_{S,T}=(-1)^{| S\cap T|}\). It is proved that the rank of any \(u\times t\) submatrix of \(A\) is at least \(ut/(2n\ln(2n/u))\). For nonsyntactic read-\(k\)-times networks (with no restrictions on inconsistent paths) the problem remains open even for \(k=2\).