scientific article; zbMATH DE number 1283999

MaRDI QIDQ4240341zbMATH OpenFDO

Authors Marek Karpinski

Publication date 3 May 1999

Full work available at URL http://www.eccc.uni-trier.de/eccc/info/call.html

zbMATH Keywords

order branching programs

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2102760
• On the complexity of randomized read-once branching programs
• scientific article; zbMATH DE number 1962823
• 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

Cited in

(13)

• scientific article; zbMATH DE number 2083801 (Why is no real title available?)
• Polynomial size \(\Omega\)-branching programs and their computational power
• scientific article; zbMATH DE number 1962823 (Why is no real title available?)
• Fractional pebbling and thrifty branching programs
• scientific article; zbMATH DE number 2123421 (Why is no real title available?)
• On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width
• On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs
• On the complexity of randomized read-once branching programs
• scientific article; zbMATH DE number 2102760 (Why is no real title available?)
• The power of nondeterminism and randomness for oblivious branching programs
• Randomization and nondeterminism are comparable for ordered read-once branching programs
• On BPP versus \(NP\cup coNP\) for ordered read-once branching programs
• On the size of randomized OBDDs and read-once branching programs for \(k\)-stable functions

This page was built for publication:

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