Characterizing the Complexity of Boolean Functions represented by Well-Structured Graph-Driven Parity-FBDDs

DOI10.1051/ita:2002011zbMath1032.68081OpenAlexW2059066560MaRDI QIDQ4800256

Matthias Homeister, Henrik Brosenne, Stephan Waack

Publication date: 15 July 2003

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

Full work available at URL: http://www.numdam.org/item?id=ITA_2002__36_3_229_0

zbMATH Keywords

polynomial time algorithm

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Specification and verification (program logics, model checking, etc.) (68Q60) Data structures (68P05)

Related Items

Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication

Cites Work

• On the size of binary decision diagrams representing Boolean functions
• Graph driven BDDs -- a new data structure for Boolean functions
• Matrix multiplication via arithmetic progressions
• Entropy of contact circuits and lower bounds on their complexity
• Linear codes are hard for oblivious read-once parity branching programs
• On the descriptive and algorithmic power of parity ordered binary decision diagrams
• Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication
• On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
• Graph-Based Algorithms for Boolean Function Manipulation
• Branching Programs and Binary Decision Diagrams
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item