On uncertainty versus size in branching programs.

DOI10.1016/S0304-3975(02)00323-7MaRDI QIDQ1401198zbMATH OpenOpenAlexFDO

Authors Stasys Jukna, Stanislav Zak

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 complexityEntropyLower boundsDecision treesKraft inequalityBranching programs

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3913677
• Stochastic Algorithms: Foundations and Applications
• New lower bounds and hierarchy results for restricted branching programs
• Pebbling, entropy and branching program size lower bounds
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs

Cites work

• scientific article; zbMATH DE number 4218008 (Why is no real title available?)
• scientific article; zbMATH DE number 2079872 (Why is no real title available?)
• scientific article; zbMATH DE number 3257409 (Why is no real title available?)
• A note on read-$k$ times branching programs
• Branching Programs and Binary Decision Diagrams
• Neither reading few bits twice nor reading illegally helps much

Cited in

(2)

• scientific article; zbMATH DE number 4047114 (Why is no real title available?)
• scientific article; zbMATH DE number 4172394 (Why is no real title available?)

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

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