Approximating Boolean functions by OBDDs

DOI10.1016/j.dam.2006.04.037zbMath1178.68257OpenAlexW2048763879MaRDI QIDQ867861

André Gronemeier

Publication date: 19 February 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2006.04.037

zbMATH Keywords

approximationcommunication complexityOBDD

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items

On the second-order nonlinearity of the hidden weighted bit function

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A lower bound for integer multiplication on randomized ordered read-once branching programs.
• Optimal lower bounds on the depth of polynomial-size threshold circuits for some arithmetic functions
• On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs
• On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
• Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions
• Graph-Based Algorithms for Boolean Function Manipulation
• On the Complexity of the Hidden Weighted Bit Function for Various BDD Models
• A Reliable Randomized Algorithm for the Closest-Pair Problem
• Branching Programs and Binary Decision Diagrams
• Read-once projections and formal circuit verification with binary decision diagrams
• Communication Complexity
• A read-once branching program lower bound of Ω(2 ^n/4 ) for integer multiplication using universal hashing