TCSLib

256 Boolean Analysis — Concentration

256.1 Overview

The low degree Fourier mass involving omitted coordinates is controlled by their influence threshold. The estimate permits endpoint noise rates and zero thresholds.

256.2 Declarations

Lemma 256.1 Fourier omission under an influence threshold
✓

Let \(f:\{ 0,1\} ^n\to \{ -1,1\} \) be a function on the uniform Boolean cube, \(J\subseteq [n]\), \(k\in \mathbb N\), \(0\le \rho \le 1\), and \(\tau \ge 0\). If \(I_i(f)\le \tau \) for every \(i\notin J\), then \(\rho ^k\sum _{|S|\le k,\ S\nsubseteq J}\widehat f(S)^2\le \tau ^{(1-\rho )/(1+\rho )}I(f)\), with \(0^0=1\). For a real cube function \(h\), define \(I_i(h)=\tfrac 14\mathbb E_x(h(x)-h(x^{(i)}))^2\), where \(x^{(i)}\) flips coordinate \(i\) and \(\mathbb E_x\) is uniform expectation, and \(I(h)=\sum _{i=0}^{n-1}I_i(h)\).