Sensitivity Versus Certificate Complexity of Boolean Functions.

Andris Ambainis Krisjanis Prusis Jevgenijs Vihrovs

Published in: CSR (2016)

Keyphrases

boolean functions
uniform distribution
polynomial size
dnf formulae
threshold functions
membership queries
relevant variables
bounded treewidth
linear threshold
prime implicants
binary decision diagrams
functional properties
multi valued
decision trees
worst case
disjunctive normal form