On Nečiporuk's theorem for branching programs

DOI10.1016/0304-3975(89)90054-6zbMATH Open0673.68027OpenAlexW2074199536MaRDI QIDQ1121017FDOQ1121017

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions

Cited In (4)

• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)