Low degree almost Boolean functions are sparse juntas.

Irit Dinur Yuval Filmus Prahladh Harsha

Published in: CoRR (2017)

Keyphrases

boolean functions
threshold functions
low degree
uniform distribution
learning theory
agnostic learning
pac learning
high dimensional
membership queries
dnf formulae
linear threshold
functional properties
disjunctive normal form
target concept
dnf formulas
machine learning
feature selection