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

DOI10.1007/3-540-63165-8_177zbMath1401.68073OpenAlexW1606189601MaRDI QIDQ4571952

Farid M. 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

Related Items (11)

On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs ⋮ On the Complexity of the Hidden Weighted Bit Function for Various BDD Models ⋮ Unnamed Item ⋮ Approximation of boolean functions by combinatorial rectangles ⋮ Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines. ⋮ Error-Free Affine, Unitary, and Probabilistic OBDDs ⋮ Randomized OBDDs for the most significant bit of multiplication need exponential space ⋮ A lower bound for integer multiplication on randomized ordered read-once branching programs. ⋮ On BPP versus \(NP\cup coNP\) for ordered read-once branching programs ⋮ Randomized OBDDs for the Most Significant Bit of Multiplication Need Exponential Size ⋮ A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the size of binary decision diagrams representing Boolean functions
• Efficient data structures for Boolean functions
• Lower bounds for one-way probabilistic communication complexity and their application to space complexity
• On lower bounds for read-\(k\)-times branching programs
• Cyclic Spaces for Grassmann Derivatives and Additive Theory

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