Noise stability of functions with low influences: invariance and optimality (Q974039)

The motivation for this paper is the study of boolean functions \(f:\{-1,1\}^n\to\{-1,1\}\), where \(\{-1,1\}^n\) is equipped with uniform probability measure. This topic is of significant interest in theoretical computer science and it is also arises in other diverse areas of mathematics. The authors prove an invariance principle for multilinear polynomials with low influences and bounded degree; it shows that under mild conditions, the distribution of such polynomials is essentially invariant for all product spaces. This result is one of the very few known nonlinear invariance principles. It has the advantage that its proof is simple and that its error bounds are explicit. They also show that the assumption of bounded degree can be eliminated if the polynomials are slightly ``smoothed'', this extension is essential for applications to ``noise stability'' type problems.