Sensitivity versus Certificate Complexity of Boolean Functions.

Andris Ambainis Krisjanis Prusis Jevgenijs Vihrovs

Published in: CoRR (2015)

Keyphrases

boolean functions
uniform distribution
polynomial size
threshold functions
relevant variables
prime implicants
dnf formulae
computational complexity
membership queries
multi valued
functional properties
truth table
pseudo boolean functions
bounded treewidth
linear threshold
read once formulas