A Noisy-Influence Regularity Lemma for Boolean Functions

Chris Jones

We present a regularity lemma for Boolean functions $f:\{-1,1{\}}^n\to \{-1,1\}$ based on noisy influence, a measure of how locally correlated $f$ is with each input bit. We provide…