On the size of randomized OBDDs and read-once branching programs for k-stable functions

DOI10.1007/S00037-001-8193-ZMaRDI QIDQ5957726zbMATH OpenOpenAlexFDO

Authors Martin Sauerhoff

Publication date 14 August 2002

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-001-8193-z

zbMATH Keywords

branching programsOBDDs

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 1283999
• scientific article; zbMATH DE number 1962823
• scientific article; zbMATH DE number 2102760
• The power of nondeterminism and randomness for oblivious branching programs
• On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs

Cited in

(10)

• scientific article; zbMATH DE number 2102760 (Why is no real title available?)
• Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.
• On BPP versus \(NP\cup coNP\) for ordered read-once branching programs
• Approximation of boolean functions by combinatorial rectangles
• Quantum branching programs and space-bounded nonuniform quantum complexity
• scientific article; zbMATH DE number 1962823 (Why is no real title available?)
• Upper and lower bounds for the \(q\)-entropy of network models with application to network model selection
• On probabilistic pushdown automata
• The power of nondeterminism and randomness for oblivious branching programs
• On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs

This page was built for publication: On the size of randomized OBDDs and read-once branching programs for \(k\)-stable functions

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