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

• scientific article; zbMATH DE number 1929932
• Lower bounds for nondeterministic semantic read-once branching programs
• scientific article; zbMATH DE number 1759409
• scientific article; zbMATH DE number 1962822
• 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
• scientific article; zbMATH DE number 1962822 (Why is no real title available?)
• Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs
• Lower bounds for nondeterministic semantic read-once branching programs
• scientific article; zbMATH DE number 1929932 (Why is no real title available?)

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)