scientific article; zbMATH DE number 17548

MaRDI QIDQ3974873zbMATH OpenFDO

Authors Matthias Krause, Stephan Waack

Publication date 26 June 1992

zbMATH Keywords

lower bounds

Mathematics Subject Classification ID

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

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

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)