A lower bound on branching programs reading some bits twice

DOI10.1016/S0304-3975(96)00183-1zbMath0911.68040OpenAlexW2042406244MaRDI QIDQ1392030

Petr Savický, Stanislav Zak

Publication date: 23 July 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(96)00183-1

zbMATH Keywords

branching programs

Mathematics Subject Classification ID

Theory of software (68N99)

Related Items (4)

Expanders and time-restricted branching programs ⋮ Neither reading few bits twice nor reading illegally helps much ⋮ A nondeterministic space-time tradeoff for linear codes ⋮ A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Neither reading few bits twice nor reading illegally helps much
• Efficient data structures for Boolean functions
• New lower bounds and hierarchy results for restricted branching programs
• On lower bounds for read-\(k\)-times branching programs
• A superpolynomial lower bound for (1,+k(n))-branching programs
• An exponential lower bound for real-time branching programs
• On the complexity of branching programs and decision trees for clique functions
• A note on read-$k$ times branching programs

This page was built for publication: A lower bound on branching programs reading some bits twice