On Nečiporuk's theorem for branching programs

DOI10.1016/0304-3975(89)90054-6MaRDI QIDQ1121017zbMATH OpenOpenAlexFDO

Authors Uri Zwick, Noga Alon

Publication date 1989

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

Full work available at URL https://doi.org/10.1016/0304-3975(89)90054-6

zbMATH Keywords

lower boundbranching programNečiporuk's theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• Nondeterminism and an abstract formulation of Nečiporuk's lower bound method
• Stochastic Algorithms: Foundations and Applications
• scientific article; zbMATH DE number 3913677
• scientific article; zbMATH DE number 5899238
• A lower bound on branching programs reading some bits twice

Cites work

• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 3257409 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions

Cited in

(4)

• scientific article; zbMATH DE number 4172394 (Why is no real title available?)
• scientific article; zbMATH DE number 4068271 (Why is no real title available?)
• Nondeterminism and an abstract formulation of Nečiporuk's lower bound method
• Characterization and lower bounds for branching program size using projective dimension

This page was built for publication: On Nečiporuk's theorem for branching programs

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