Subquadratic Simulations of Balanced Formulae by Branching Programs

DOI10.1137/S0097539790181336MaRDI QIDQ4302284zbMATH OpenFDO

Authors Jin-Yi Cai, Richard J. Lipton

Publication date 14 August 1994

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539790181336

zbMATH Keywords

Boolean circuitsBoolean formulaebounded width branching programspermutation branching programs

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Branching program size is almost linear in formula size
• scientific article; zbMATH DE number 1304312
• Towards optimal simulations of formulas by bounded-width programs
• scientific article; zbMATH DE number 3913677
• scientific article; zbMATH DE number 36617

Cited in

(3)

• Efficient oblivious branching programs for threshold and mod functions
• Branching program size is almost linear in formula size
• Towards optimal simulations of formulas by bounded-width programs

This page was built for publication: Subquadratic Simulations of Balanced Formulae by Branching Programs

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