The Complexity of Boolean Functions in Different Characteristics.

Parikshit Gopalan Amir Shpilka Shachar Lovett

Published in: Comput. Complex. (2010)

Keyphrases

boolean functions
uniform distribution
polynomial size
functional properties
prime implicants
threshold functions
multi valued
relevant variables
worst case
computational complexity
dnf formulae
membership queries
bi decomposition
search algorithm