On uncertainty versus size in branching programs.

DOI10.1016/S0304-3975(02)00323-7zbMath1044.68064OpenAlexW2050347452MaRDI QIDQ1401198

Stanislav Zak, Stasys P. Jukna

Publication date: 17 August 2003

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00323-7

zbMATH Keywords

Computational complexityDecision treesEntropyLower boundsKraft inequalityBranching programs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Neither reading few bits twice nor reading illegally helps much
• A note on read-$k$ times branching programs
• Branching Programs and Binary Decision Diagrams
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On uncertainty versus size in branching programs.