On the Degree of Boolean Functions as Real Polynomials.

Noam Nisan Mario Szegedy

Published in: Comput. Complex. (1994)

Keyphrases

boolean functions
uniform distribution
threshold functions
prime implicants
membership queries
multi valued
dnf formulae
functional properties
read once formulas
polynomial size
machine learning
linear functions
relevant variables