A lower bound technique for nondeterministic graph-driven read-once-branching programs and its applications

DOI10.1007/S00224-004-1130-1MaRDI QIDQ2581005zbMATH OpenOpenAlexFDO

Authors Beate Bollig, Philipp Woelfel

Publication date 10 January 2006

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-004-1130-1

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A lower bound technique for nondeterministic graph-driven read-once-branching programs and its applications
• Lower bounds for nondeterministic semantic read-once branching programs
• Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication (extended abstract)
• Complexity theoretical results on nondeterministic graph-driven read-once branching programs
• Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication

Cited in

(8)

• A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs
• New results on the most significant bit of integer multiplication
• On the OBDD complexity of the most significant bit of integer multiplication
• On the OBDD Complexity of the Most Significant Bit of Integer Multiplication
• Complexity theoretical results on nondeterministic graph-driven read-once branching programs
• Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs
• Lower bounds for nondeterministic semantic read-once branching programs
• A lower bound technique for nondeterministic graph-driven read-once-branching programs and its applications

This page was built for publication: A lower bound technique for nondeterministic graph-driven read-once-branching programs and its applications

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