Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs

DOI10.1051/ITA:2003010MaRDI QIDQ4462678zbMATH OpenOpenAlexFDO

Authors Beate Bollig

Publication date 18 May 2004

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL http://www.numdam.org/item?id=ITA_2003__37_1_51_0, https://eudml.org/doc/92713, https://semanticscholar.org/paper/a7cb45c36a032329180ceb1198ccbbd4a80d6bd7

zbMATH Keywords

Computational complexitylower boundsnondeterminismread-once branching programs

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 1962822
• A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs
• scientific article; zbMATH DE number 1929932
• scientific article; zbMATH DE number 4047115
• A lower bound technique for nondeterministic graph-driven read-once-branching programs and its applications

Cites work

• A comparison of free BDDs and transformed BDDs
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• Branching Programs and Binary Decision Diagrams
• Communication Complexity
• Efficient Boolean manipulation with OBDD's can be extended to FBDD's
• Graph driven BDDs -- a new data structure for Boolean functions
• Graph-Based Algorithms for Boolean Function Manipulation
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 512863 (Why is no real title available?)
• scientific article; zbMATH DE number 1011685 (Why is no real title available?)
• scientific article; zbMATH DE number 1759451 (Why is no real title available?)
• scientific article; zbMATH DE number 1775455 (Why is no real title available?)
• scientific article; zbMATH DE number 1929932 (Why is no real title available?)
• scientific article; zbMATH DE number 2086405 (Why is no real title available?)
• scientific article; zbMATH DE number 2086709 (Why is no real title available?)
• scientific article; zbMATH DE number 1834649 (Why is no real title available?)
• scientific article; zbMATH DE number 3257409 (Why is no real title available?)
• On lower bounds for read-\(k\)-times branching programs
• Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication
• Probabilistic verification of Boolean functions
• Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication
• Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems

Cited in

(6)

• A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs
• Modified branching programs and their computational power
• A hierarchy result for read-once branching programs with restricted parity nondeterminism
• scientific article; zbMATH DE number 4047115 (Why is no real title available?)
• scientific article; zbMATH DE number 1962822 (Why is no real title available?)
• scientific article; zbMATH DE number 1929932 (Why is no real title available?)

This page was built for publication: Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs

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