On Nečiporuk's theorem for branching programs

DOI10.1016/0304-3975(89)90054-6zbMath0673.68027OpenAlexW2074199536MaRDI QIDQ1121017

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)

Cites Work

• A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
• Unnamed Item
• Unnamed Item
• Unnamed Item

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