Branching program size is almost linear in formula size

DOI10.1006/JCSS.2001.1762MaRDI QIDQ5956012zbMATH OpenOpenAlexFDO

Authors Oliver Giel

Publication date 11 September 2002

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcss.2001.1762

zbMATH Keywords

Boolean functionscomplexity measures

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Subquadratic Simulations of Balanced Formulae by Branching Programs
• Relating branching program size and formula size over the full binary basis
• Size-depth tradeoffs for Boolean formulae
• Towards optimal simulations of formulas by bounded-width programs
• scientific article; zbMATH DE number 3913677

Cites work

• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 3737545 (Why is no real title available?)
• Relating branching program size and formula size over the full binary basis
• Size-depth tradeoffs for Boolean formulae
• Towards optimal simulations of formulas by bounded-width programs

Cited in

(7)

• Reduced error pruning of branching programs cannot be approximated to within a logarithmic factor
• Size-depth tradeoffs for Boolean formulae
• Relating branching program size and formula size over the full binary basis
• Subquadratic Simulations of Balanced Formulae by Branching Programs
• A note on amortized branching program complexity
• Towards optimal simulations of formulas by bounded-width programs
• Partial minimum branching program size problem is ETH-hard

This page was built for publication: Branching program size is almost linear in formula size

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