Randomization and nondeterminism are comparable for ordered read-once branching programs

DOI10.1007/3-540-63165-8_177MaRDI QIDQ4571952zbMATH OpenOpenAlexFDO

Authors F. Ablayev

Publication date 4 July 2018

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-63165-8_177

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 2102760
• scientific article; zbMATH DE number 1962823
• scientific article; zbMATH DE number 1283999
• On BPP versus \(NP\cup coNP\) for ordered read-once branching programs
• On the complexity of randomized read-once branching programs

Cites work

• Cyclic Spaces for Grassmann Derivatives and Additive Theory
• Efficient data structures for Boolean functions
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 1263188 (Why is no real title available?)
• scientific article; zbMATH DE number 549860 (Why is no real title available?)
• scientific article; zbMATH DE number 2102760 (Why is no real title available?)
• Lower bounds for one-way probabilistic communication complexity and their application to space complexity
• On lower bounds for read-\(k\)-times branching programs
• On the size of binary decision diagrams representing Boolean functions

Cited in

(17)

• Approximation of boolean functions by combinatorial rectangles
• Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.
• A lower bound for integer multiplication on randomized ordered read-once branching programs.
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• Randomized OBDDs for the most significant bit of multiplication need exponential space
• On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-k-times branching programs
• Randomized OBDDs for the most significant bit of multiplication need exponential size
• scientific article; zbMATH DE number 1283990 (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
• scientific article; zbMATH DE number 1962823 (Why is no real title available?)
• scientific article; zbMATH DE number 2102760 (Why is no real title available?)
• scientific article; zbMATH DE number 2123421 (Why is no real title available?)
• scientific article; zbMATH DE number 7092118 (Why is no real title available?)
• Improved pseudorandomness for unordered branching programs through local monotonicity
• On BPP versus \(NP\cup coNP\) for ordered read-once branching programs
• Error-Free Affine, Unitary, and Probabilistic OBDDs

This page was built for publication: Randomization and nondeterminism are comparable for ordered read-once branching programs

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