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\), \(T\subseteq [n]\), \(x\in \Omega \), and \(\tau \in \mathbb R\). The restriction \((T,x)\) is a \(\tau \)-booster if either \(\tau \gt 0\) and \(\mathbb E_Pf+\tau \le E_Tf(x)\), or \(\tau \lt 0\) and \(E_Tf(x)\le \mathbb E_Pf+\tau \).

Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), sets \(J_j\subseteq [n]\) and tests \(b_j:\Omega \to \{ 0,1\} \) indexed by \(j\in \{ 0,\ldots ,m-1\} \). Define \(J(x)=\bigcup _{j:b_j(x)=1}J_j\).

Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), sets \(J_j\subseteq [n]\) and tests \(b_j:\Omega \to \{ 0,1\} \) for \(j\lt m\). The observation at \(x\) records \(x_i\) when \(i\in \bigcup _{j:b_j(x)=1}J_j\), and records a distinguished missing symbol otherwise.

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 \mathbb R\), and \(K\in \mathbb R\). Say that \(h\) is a \(K\)-pseudo-junta if there exist finitely many sets \(J_j\subseteq [n]\), tests \(b_j:\Omega \to \{ 0,1\} \) depending only on \(J_j\), and a real function of the coordinate observations such that \(h(x)\) is determined by the values on \(J(x)=\bigcup _{j:b_j(x)=1}J_j\), including knowledge of \(J(x)\) itself, and \(\mathbb E_P|J(x)|\le K\).

For every \(p\in \mathbb R\) and an event \(A\subseteq \{ 0,1\} ^n\), define \(\Pr _p(A)=\sum _x\prod _i[p\mathbf1_{x_i=1}+(1-p)\mathbf1_{x_i=0}]\mathbf1_A(x)\). For \(0\le p\le 1\) this is independent Bernoulli-\(p\) probability; the formula defines a polynomial for every real \(p\).

For every \(f:\{ 0,1\} ^n\to \{ 0,1\} \) and \(p\in \mathbb R\), define \(\theta _f(p)=\sum _x\prod _i[p\mathbf1_{x_i=1}+(1-p)\mathbf1_{x_i=0}]\mathbf1_{f(x)=1}\). On \([0,1]\) this is the Bernoulli-\(p\) probability of output \(1\).

A function \(f:\{ 0,1\} ^n\to \{ 0,1\} \) is increasing if \(x_i\le y_i\) for every coordinate implies \(f(x)\le f(y)\), with \(0\lt 1\).

A function \(f:\{ 0,1\} ^n\to \{ 0,1\} \) is transitively symmetric if for every \(i,j\in [n]\) there exists a permutation \(\sigma \) of \([n]\) with \(\sigma (i)=j\) and \(f(x\circ \sigma )=f(x)\) for every \(x\).

For every \(p\in \mathbb R\) and \(f:\{ 0,1\} ^n\to \{ 0,1\} \), define \(I_p(f)=4p(1-p)\sum _i\Pr _p(f(x^{i\leftarrow 0})\ne f(x^{i\leftarrow 1}))\), using the polynomial Bernoulli-\(p\) weights when \(p\) is outside \([0,1]\).

For every \(v\in \mathbb N\), the edges on the labeled vertex set \(\{ 0,\ldots ,v-1\} \) are its two-element subsets.

Let \(e:[n]\to \binom {[v]}2\) be a bijection and \(f:\{ 0,1\} ^n\to \{ 0,1\} \). Say that \(f\) is a graph property if for every vertex permutation \(\sigma \) and inputs \(x,y\) satisfying \(y_j=x_i\) whenever \(e(j)=\sigma (e(i))\), one has \(f(y)=f(x)\).

A disjunctive normal form formula on \(n\) Boolean variables is monotone if every literal in every term is a positive variable, without negation.