A lower bound for read-once-only branching programs

DOI10.1016/0022-0000(87)90010-9MaRDI QIDQ1107323zbMATH OpenOpenAlexFDO

Authors Péter Hajnal, Gy. Turán, László Babai, Endre Szemerédi

Publication date 1987

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(87)90010-9

zbMATH Keywords

complexitylower boundsbranching programseraser RAM

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 549860
• The optimal read-once branching program complexity for the direct storage access function
• A very simple function that requires exponential size read-once branching programs.
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• scientific article; zbMATH DE number 3890736

Cites work

• scientific article; zbMATH DE number 3866582 (Why is no real title available?)
• scientific article; zbMATH DE number 3890736 (Why is no real title available?)
• scientific article; zbMATH DE number 3913677 (Why is no real title available?)
• scientific article; zbMATH DE number 4008289 (Why is no real title available?)
• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 3711961 (Why is no real title available?)
• scientific article; zbMATH DE number 3566175 (Why is no real title available?)
• scientific article; zbMATH DE number 3594626 (Why is no real title available?)
• scientific article; zbMATH DE number 3999837 (Why is no real title available?)
• scientific article; zbMATH DE number 3257409 (Why is no real title available?)
• A time-space tradeoff for sorting on non-oblivious machines
• The monotone circuit complexity of Boolean functions

Cited in

(19)

• scientific article; zbMATH DE number 1775455 (Why is no real title available?)
• On the hierarchy of nondeterministic branching k-programs
• Satisfiable Tseitin formulas are hard for nondeterministic read-once branching programs
• Neither reading few bits twice nor reading illegally helps much
• Paradigms for Unconditional Pseudorandom Generators
• Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus
• scientific article; zbMATH DE number 61460 (Why is no real title available?)
• A simple function that requires exponential size read-once branching programs
• A very simple function that requires exponential size read-once branching programs.
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• Reduced error pruning of branching programs cannot be approximated to within a logarithmic factor
• On the size of binary decision diagrams representing Boolean functions
• scientific article; zbMATH DE number 1332670 (Why is no real title available?)
• A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3
• On lower bounds for read-\(k\)-times branching programs
• Time-space tradeoffs for branching programs
• A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs
• scientific article; zbMATH DE number 2079872 (Why is no real title available?)
• Read-Once Branching Programs for Tree Evaluation Problems

This page was built for publication: A lower bound for read-once-only branching programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1107323)