On the complexity of randomized read-once branching programs

MaRDI QIDQ3013174zbMATH OpenFDO

Authors R. G. Mubarakzyanov

Publication date 18 July 2011

zbMATH Keywords

binary branching programBoolean functioncomplexity classcomputation complexity lower bound

Mathematics Subject Classification ID

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

Recommendations

• A lower bound for integer multiplication on randomized ordered read-once branching programs.
• scientific article; zbMATH DE number 1283999
• scientific article; zbMATH DE number 1759409
• scientific article; zbMATH DE number 2102760
• Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication

Cited in

(9)

• A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs
• A lower bound for integer multiplication on randomized ordered read-once branching programs.
• scientific article; zbMATH DE number 1283999 (Why is no real title available?)
• scientific article; zbMATH DE number 1332670 (Why is no real title available?)
• scientific article; zbMATH DE number 2079872 (Why is no real title available?)
• Randomization and nondeterminism are comparable for ordered read-once branching programs
• Read-once projections and formal circuit verification with binary decision diagrams
• scientific article; zbMATH DE number 2083801 (Why is no real title available?)
• Read-Once Branching Programs for Tree Evaluation Problems

This page was built for publication: On the complexity of randomized read-once branching programs

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