2016/10/21 by Chris Jones, Jones, Chris · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Machine Learning and Algorithms #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1610.06950
We present a regularity lemma for Boolean functions f:\-1,1\n → \-1,1\ based on noisy influence, a measure of how locally correlated f is with each input bit. We provide an application of the regularity lemma to weaken the conditions on the Majority is Stablest Theorem. We also prove a "homogenized" version stating that there is a set of input bits so that most restrictions of f on those bits have small noisy influences. These results were sketched out by [OSTW10], but never published. With their permission, we present the full details here.