Feature Selection and Junta Testing are Statistically Equivalent

Lorenzo Beretta, Nathaniel Harms, Caleb Koch

For a function $f:\{0,1{\}}^n\to \{0,1\}$, the junta testing problem asks whether $f$ depends on only $k$ variables. If $f$ depends on only $k$ variables, the feature selecti…