On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs
type: Item
instance of: scholarly article
title: On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs
zbMATH Open document ID: 1012.68086
DOI: 10.1016/S0890-5401(02)93174-3
author: Beate Bollig
author: Martin Sauerhoff
author: Ingo Wegener
published in: Information and Computation
publication date: 2003-01-14T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68T05
zbMATH DE Number: 1853292
MaRDI profile type: Publication
cites work: Determinism versus non-determinism for linear time RAMs (extended abstract)
cites work: Meanders and their applications in lower bounds arguments
cites work: Q4542591
cites work: Time-space tradeoffs for branching programs
cites work: Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems
cites work: On lower bounds for read-\(k\)-times branching programs
cites work: Lower bounds for depth-restricted branching programs
cites work: Separating $\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious Turing machines of linear access
cites work: On randomized one-round communication complexity
cites work: Communication Complexity
cites work: On the size of randomized OBDDs and read-once branching programs for \(k\)-stable functions
cites work: Branching Programs and Binary Decision Diagrams
description: scientific article; zbMATH DE number 1853292