On the structure of boolean functions with small spectral norm.

Amir Shpilka Avishay Tal Ben lee Volk

Published in: ITCS (2014)

Keyphrases

boolean functions
functional properties
uniform distribution
functional decomposition
prime implicants
relevant variables
dnf formulae
membership queries
read once formulas
threshold functions
learning algorithm
objective function
multi valued
binary decision diagrams
truth table