On the Degree of Polynomials that Approximate Symmetric Boolean Functions (Preliminary Version)

Ramamohan Paturi

Published in: STOC (1992)

Keyphrases

boolean functions
preliminary version
uniform distribution
linear functions
threshold functions
prime implicants
membership queries
dnf formulae
dnf formulas
disjunctive normal form
polynomial size
read once formulas
functional properties
relevant variables
machine learning
multi valued
lower bound