On the power of randomized branching programs

DOI10.1007/3-540-61440-0_141MaRDI QIDQ4818848zbMATH OpenFDO

Authors F. Ablayev, Marek Karpinski

Publication date 24 September 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-61440-0_141

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 1283999
• Randomness versus nondeterminism for read-once and read-k branching programs
• Randomization and nondeterminism are comparable for ordered read-once branching programs
• On the size of randomized OBDDs and read-once branching programs for k-stable functions
• scientific article; zbMATH DE number 2123421

Cited in

(29)

• Approximation of boolean functions by combinatorial rectangles
• A lower bound for integer multiplication on randomized ordered read-once branching programs.
• Randomized OBDDs for the most significant bit of multiplication need exponential space
• New size hierarchies for two way automata
• A deterministic algorithm for testing the equivalence of read-once branching programs with small discrepancy
• Very narrow quantum OBDDs and width hierarchies for classical OBDDs
• On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-k-times branching programs
• Nondeterministic unitary OBDDs
• The hierarchical model of branch planning with random coefficients
• On the computational power of probabilistic and quantum branching program
• Fractional pebbling and thrifty branching programs
• On the complexity of randomized read-once branching programs
• Randomized OBDDs for the most significant bit of multiplication need exponential size
• scientific article; zbMATH DE number 17548 (Why is no real title available?)
• scientific article; zbMATH DE number 1283999 (Why is no real title available?)
• On the Complexity of the Hidden Weighted Bit Function for Various BDD Models
• Randomness versus nondeterminism for read-once and read-k branching programs
• Randomization and nondeterminism are comparable for ordered read-once branching programs
• A direct-sum theorem for read-once branching programs
• Randomized branching programs
• scientific article; zbMATH DE number 2123421 (Why is no real title available?)
• A note on amortized branching program complexity
• Improved pseudorandomness for unordered branching programs through local monotonicity
• On BPP versus \(\text{NP}\cup \text{coNP}\) for ordered read-once branching programs
• On the size of randomized OBDDs and read-once branching programs for k-stable functions
• Branch-and-bound solves random binary IPs in poly(n)-time
• Classical and Quantum Computations with Restricted Memory
• Error-Free Affine, Unitary, and Probabilistic OBDDs
• Polynomial size \(\Omega\)-branching programs and their computational power

This page was built for publication: On the power of randomized branching programs

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