scientific article; zbMATH DE number 17548

zbMATH Open0756.68042MaRDI QIDQ3974873FDOQ3974873

Matthias Krause, Stephan Waack

Publication date: 26 June 1992

Title of this publication is not available (Why is that?)

Recommendations

• On oblivious branching programs of linear length
• scientific article; zbMATH DE number 827986
• scientific article; zbMATH DE number 4172378
• Efficient oblivious branching programs for threshold and mod functions
• The power of nondeterminism and randomness for oblivious branching programs
• On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth
• scientific article; zbMATH DE number 706832
• scientific article; zbMATH DE number 2102760
• Stochastic Algorithms: Foundations and Applications
• scientific article; zbMATH DE number 3913677

zbMATH Keywords

lower bounds

Mathematics Subject Classification ID

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

Cited In (4)

• Separating $\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious Turing machines of linear access
• Tight Bounds on Oblivious Chaining
• Separating counting communication complexity classes
• Oracle branching programs and Logspace versus \(P^*\)

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 Q3974873)