On the Nonapproximability of Boolean Functions by OBDDs and Read-k-Times Branching Programs.

Beate Bollig Martin Sauerhoff Ingo Wegener

Published in: Inf. Comput. (2002)

Keyphrases

boolean functions
uniform distribution
randomly generated
threshold functions
prime implicants
membership queries
relevant variables
disjunctive normal form
read once formulas
multi valued
linear threshold
truth table
binary decision diagrams
dnf formulas
dnf formulae