There exists an absolute \(B\gt 0\) such that for every \(n\ge 2\), nonconstant increasing transitively symmetric \(f:\{ 0,1\} ^n\to \{ 0,1\} \), \(0\lt p_c\le 1/2\) with \(\Pr _{p_c}(f=1)=1/2\), and \(0\lt \varepsilon \lt 1/4\), the number \(\eta =B\log (1/\varepsilon )\log (1/p_c)/\log n\) satisfies: if \(\eta \le 1/2\), then \(\Pr _{p_c(1-\eta )}(f=1)\le \varepsilon \) and \(\Pr _{p_c(1+\eta )}(f=1)\ge 1-\varepsilon \).

There exists \(w:\mathbb R\times \mathbb R\to \mathbb N\) such that whenever the \(n\) variables bijectively index the edges of a labeled simple graph on \(v\) vertices, \(f:\{ 0,1\} ^n\to \{ 0,1\} \) is an increasing graph property, \(0\lt p\le 1/2\), \(K\gt 0\), \(0\lt \varepsilon \lt 1\), and \(I_p(f)\le K\), there is a monotone DNF \(d\) of width at most \(w(K,\varepsilon )\) with \(\Pr _p(f\ne d)\le \varepsilon \). Here \(I_p(f)=4p(1-p)\) times the sum of pivotal probabilities.

There are absolute \(C,D\gt 0\) such that for every product \(P\) of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), every \(f:\Omega \to \{ -1,1\} \), and every real \(K\) satisfying \(I(f)\le K\) and \(\operatorname {Var}_P(f)\ge 1/100\), there exists \(\tau \in \mathbb R\) with \(e^{-CK^2}\le |\tau |\le \Pr _P(\exists T\subseteq [n],\ |T|\le DK:\ (T,x)\text{ is a }\tau \text{-booster})\). A \(\tau \)-booster has \(E_Tf(x)\ge \mathbb E_Pf+\tau \) for \(\tau \gt 0\), or \(E_Tf(x)\le \mathbb E_Pf+\tau \) for \(\tau \lt 0\).

There is an absolute \(C\gt 0\) such that for every product \(P\) of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), every \(f:\Omega \to \{ -1,1\} \), \(K\ge 0\) with \(I(f)\le K\), and \(\varepsilon \gt 0\), there is \(h:\Omega \to \{ -1,1\} \) with \(\Pr _P(f\ne h)\le \varepsilon \) that is determined by locally triggered coordinate observations exposing at most \(\exp (CK^3/\varepsilon ^3)\) coordinates in expectation.

Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), \(h:\Omega \to \{ -1,1\} \), and \(K\in \mathbb R\). If \(h\) is determined by locally triggered coordinate observations whose expected exposed size is at most \(K\), with each trigger depending only on its declared coordinate set, then \(I(h)\le 4K\).

There are absolute \(C,D\gt 0\) such that for every product \(P\) of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), every \(f:\Omega \to \{ -1,1\} \), and \(0\lt \varepsilon \lt 1/2\), putting \(k=I(f)/\varepsilon \), there exist sets \(J(x)\subseteq [n]\) satisfying \(|J(x)|\le e^{Ck}\) and \(|\{ S\subseteq J(x):|S|\le k\} |\le e^{Dk^2}\) for every \(x\), and \(\mathbb E_P\sum _{S\notin \{ T\subseteq J(x):|T|\le k\} }f_S(x)^2\le 2\varepsilon \).

Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), \(f:\Omega \to \mathbb R\), \(x\in \Omega \), a coordinate \(i\), and \(\tau \gt 0\). If \(\sum _{S\ni i}f_S(x)^2\lt \tau \), put \(g=T_{2/5}L_if\) and \(h(r)=\sum _S\chi _S(r)g_S(x)\); then on the uniform sign cube \(\| T_{1/\sqrt3}h\| _2^2\le \tau ^{1/3}\| h\| _{4/3}^{4/3}\).