Approximate resilience, monotonicity, and the complexity of agnostic learning

Dana Dachman-Soled, Vitaly Feldman, Li-Yang Tan +2

A function $f$ is $d$-resilient if all its Fourier coefficients of degree at most $d$ are zero, i.e., $f$ is uncorrelated with all low-degree parities. We study the notion of $\mat…