On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs

DOI10.1016/S0890-5401(02)93174-3zbMath1012.68086MaRDI QIDQ1854567

Martin Sauerhoff, Beate Bollig, Ingo Wegener

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05)

Related Items (3)

Approximating Boolean functions by OBDDs ⋮ Approximation of boolean functions by combinatorial rectangles ⋮ On the influence of the variable ordering for algorithmic learning using OBDDs

Cites Work

• Unnamed Item
• Meanders and their applications in lower bounds arguments
• Lower bounds for depth-restricted branching programs
• On randomized one-round communication complexity
• Time-space tradeoffs for branching programs
• On lower bounds for read-\(k\)-times branching programs
• Determinism versus non-determinism for linear time RAMs (extended abstract)
• Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems
• Separating $\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious Turing machines of linear access
• Branching Programs and Binary Decision Diagrams
• Communication Complexity
• On the size of randomized OBDDs and read-once branching programs for \(k\)-stable functions

This page was built for publication: On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs