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
• Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication (extended abstract)
• On the power of randomized branching programs
• 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?)
• Some notes on the information flow in read-once branching programs
• Randomization and nondeterminism are comparable for ordered read-once branching programs
• Read-once projections and formal circuit verification with binary decision diagrams
• Randomized branching programs
• 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)