Fetching the paper…

Reading the bibliography…

A Noisy-Influence Regularity Lemma for Boolean Functions · Around

2016

A Noisy-Influence Regularity Lemma for Boolean Functions

Jones, Chris

Original
PDF
Post on X

Understand

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 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.

Built on

Noise stability of functions with low influences: Invariance and optimality
E. Mossel, R. O’Donnell, and K. Oleszkiewicz · 2005
Earlier work this paper cites.
A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions
Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, and Andrew Wan · 2009
Earlier work this paper cites.

Similar

Regularity, boosting, and efficiently simulating every high-entropy distribution
Original
Luca Trevisan, Madhur Tulsiani, and Salil Vadhan · 2009
Cited alongside, same era.
A regularity lemma for low noisy-influences
Ryan O’Donnell, Rocco Servedio, Li-Yang Tan, and Andrew Wan · 2010
Cited alongside, same era.
A szemeredi-type regularity lemma in abelian groups, with applications
Ben Green
Cited in the paper.

Then

An improved lower bound for arithmetic regularity
Kaave Hosseini, Shachar Lovett, Guy Moshkovitz, and Asaf Shapira · 2014
Later among the works it cites.
Analysis of Boolean Functions
Ryan O’Donnell · 2014
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…