A structure theorem for Boolean functions with small total influences
This article deals with Boolean (i.e., \(\{0,1\}\)-valued) functions on the product space \(X^{n}\), where \(X\) is a probability space. For \(1\leq j\leq n\) we say the influence of the \(j\)th variable on \(f\) is NEWLINENEWLINE\[NEWLINEI_{f}(j) = NEWLINE\mathbb{P}\bigl[f(x_{1},\ldots x_{j-1},x_{j},x_{j+1}\ldots x_{n})\neq \mathbb{P}(x_{1},\ldots x_{j},y_{j},x_{j+1},\ldots x_{n})\bigr]NEWLINE\]NEWLINENEWLINEwhere the \(x_{i}\)s and \(y_{i}\)s are independent random variables, all distributed according to the probability measure on \(X\). Informally, it measures the sensitivity of a function to a change of that variable. NEWLINENEWLINENEWLINE NEWLINEThe main result of the paper under review is basically to show that any measurable Boolean function on \(X^{n}\) can be approximated by a special kind of function, a so-called \(k\)-pseudo junta for a suitable \(k\) depending on the influence of \(f\) \textit{but not on} \(n\). More precisely, given a measurable function NEWLINE\(f: X^{n}\rightarrow \{0,1\}\) and \(\epsilon>0\) there is an \(e^{10^{15}\epsilon^{-3}\lceil I_{f}\rceil ^{3}}\)-pseudo junta such that the \(L_{1}\)-norm \(\parallel f-h\parallel_{1}\leq \epsilon\). NEWLINENEWLINENEWLINE NEWLINEHere a \(k\)-pseudo junta is defined as follows. Given a collection \({\mathcal J}=\{J_{S}\}\), where \(S\) ranges over subsets of \([n]=\{1,2,\ldots n\}\), of measurable functions \(J_{S}: X^{S}\rightarrow \{0,1\}\) we define a map \(J_{\mathcal J}: X^{n}\rightarrow {\mathcal P}([n])\) by \(J_{\mathcal J}(x)=\bigcup_{S\subseteq [n], J_{S}(x)=1}S\) and let \({\mathcal F}_{\mathcal J}\) be the \(\sigma\)-algebra induced by the (measurable) function \(x\rightarrow (J_{\mathcal J}( x),x_{J_{\mathcal J}(x)})\), i.e. the coarsest \(\sigma\)-algebra on \(X^{n}\) with respect to which this function is measurable. Then we say a \(k\)-pseudo junta is a Boolean function on \(X^{n}\) measurable with respect to \({\mathcal F}_{\mathcal J}\) for some \({\mathcal J}\) such that \(\int | J_{\mathcal J}(x)| dx \leq k\). To explain the term pseudo-junta, note that if \(A\subseteq [n]\) with \(| A| \leq k\) every measurable Boolean function on \(X^{n}\) which depends only on co-ordinates in \(A\) (when \(k\) is small, this is what has in previous literature been called a junta) is a \(k\)-pseudo junta (define \({\mathcal J}\) by saying \(J_{S}\equiv 1\) if \(S=A\) and \(J_{S}\equiv 0\) otherwise). It is not hard to show that a \(k\)-pseudo junta \(f\) has \(I_{f}\leq 2k\): the main result above is in some sense an inverse result to this observation. NEWLINENEWLINENEWLINE NEWLINEConsequences include an improvement of a result of Bourgain: the (new) result says that, given an increasing Boolean function \(f\) on \(\{0,1\}^{n}\) with the Bernoulli measure on \(X\) (i.e., we get 1 with probability \(p\), 0 with probability \(1-p\)) for which \(\int f=\alpha >0\), and given \(\epsilon>0\), for \(p\leq 1/2\) there is \(S\subseteq [n]\) with \(| S| \leq e^{10^{12}\lceil I_{f}\rceil ^{2}\alpha^{-2}\epsilon^{-2}}\) such that \(\mathbb{E}(f(x)| x_{S}=(1,1,\ldots 1))\geq 1-\epsilon\). Here again \(x\) takes values in \(\{0,1\}^{n}\) according to the product Bernoulli distribution, and \(x_{S}\) denotes \((x_{i}:\, i\in S)\). NEWLINENEWLINENEWLINE NEWLINEThe paper also notes why such results are of interest in the theory of threshold phenomena and their sharpness in e.g. statistical physics and in hardness of approximation in theoretical computer science, and notes that a more general conjecture of Friedgut on increasing graph properties [\textit{E. Friedgut}, ``Sharp thresholds of graph properties, and the \(k\)-sat problem,'' J. Am. Math. Soc. 12, No. 4, 1017--1054 (1999; Zbl 0932.05084)] remains open.
scientific article; zbMATH DE number 6074020
scientific article