A structure theorem for Boolean functions with small total influences (Q447936): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / review text | |||
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 \[ I_{f}(j) = \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] \] where 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. The 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 \(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\). Here 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. Consequences 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)\). The 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. | |||
Property / review text: 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 \[ I_{f}(j) = \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] \] where 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. The 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 \(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\). Here 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. Consequences 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)\). The 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. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: David B. Penman / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C80 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 06E30 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 94C10 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6074020 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Boolean function | |||
Property / zbMATH Keywords: Boolean function / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
influence | |||
Property / zbMATH Keywords: influence / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
phase transition | |||
Property / zbMATH Keywords: phase transition / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
threshold | |||
Property / zbMATH Keywords: threshold / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
pseudo-junta | |||
Property / zbMATH Keywords: pseudo-junta / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2963226739 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1008.1021 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2784326 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Sharp thresholds of graph properties, and the $k$-sat problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4501769 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The influence of variables in product spaces / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Influences of variables and threshold intervals under group symmetries / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The jackknife estimate of variance / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Boolean functions with low average sensitivity depend on few coordinates / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Hunting for sharp thresholds / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Every monotone graph property has a sharp threshold / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Decision Trees and Influences of Variables Over Product Probability Spaces / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Class of Statistics with Asymptotically Normal Distribution / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4083487 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Noise stability of functions with low influences: invariance and optimality / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the critical percolation probabilities / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An approximate zero-one law / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Russo's approximate zero-one law / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 15:27, 5 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A structure theorem for Boolean functions with small total influences |
scientific article |
Statements
A structure theorem for Boolean functions with small total influences (English)
0 references
30 August 2012
0 references
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 \[ I_{f}(j) = \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] \] where 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. The 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 \(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\). Here 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. Consequences 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)\). The 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.
0 references
Boolean function
0 references
influence
0 references
phase transition
0 references
threshold
0 references
pseudo-junta
0 references