Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism

Eric Blais, Clément L. Canonne, Talya Eden +2

A function $f:\{-1,1{\}}^n\to \{-1,1\}$ is a $k$-junta if it depends on at most $k$ of its variables. We consider the problem of tolerant testing of $k$-juntas, where the test…