Low degree almost Boolean functions are sparse juntas.

Irit Dinur Yuval Filmus Prahladh Harsha

Published in: Electron. Colloquium Comput. Complex. (2017)

Keyphrases

boolean functions
threshold functions
low degree
uniform distribution
learning theory
membership queries
pac learning
agnostic learning
high dimensional
linear threshold
dnf formulae
multi valued
functional properties
machine learning
linear combination
disjunctive normal form