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

From MaRDI portal
Added link to MaRDI item.
RedirectionBot (talk | contribs)
Removed claims
Property / author
 
Property / author: Roman Smolensky / rank
Normal rank
 
Property / reviewed by
 
Property / reviewed by: Stasys P. Jukna / rank
Normal rank
 

Revision as of 07:06, 22 February 2024

scientific article
Language Label Description Also known as
English
On lower bounds for read-\(k\)-times branching programs
scientific article

    Statements

    On lower bounds for read-\(k\)-times branching programs (English)
    0 references
    0 references
    0 references
    30 August 1993
    0 references
    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\).
    0 references
    read-\(k\)-times networks
    0 references
    generalized Fourier transforms
    0 references
    lower bounds
    0 references
    branching programs
    0 references

    Identifiers