A structure theorem for Boolean functions with small total influences
type: Item
instance of: scholarly article
title: A structure theorem for Boolean functions with small total influences
zbMATH Open document ID: 1253.05128
author: Hamed Hatami
published in: Annals of Mathematics. Second Series
publication date: 2012-08-30T00:00:00Z
full work available at URL: https://arxiv.org/abs/1008.1021
reviewed by: David B. Penman
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 06E30
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 6074020
zbMATH Keywords: Boolean function
zbMATH Keywords: influence
zbMATH Keywords: phase transition
zbMATH Keywords: threshold
zbMATH Keywords: pseudo-junta
MaRDI profile type: Publication
OpenAlex ID: W2963226739
arXiv ID: 1008.1021
cites work: The probabilistic method. With an appendix on the life and work of Paul Erdős.
cites work: Sharp thresholds of graph properties, and the $k$-sat problem
cites work: Q4501769
cites work: The influence of variables in product spaces
cites work: Influences of variables and threshold intervals under group symmetries
cites work: The jackknife estimate of variance
cites work: Boolean functions with low average sensitivity depend on few coordinates
cites work: Hunting for sharp thresholds
cites work: Every monotone graph property has a sharp threshold
cites work: Decision Trees and Influences of Variables Over Product Probability Spaces
cites work: A Class of Statistics with Asymptotically Normal Distribution
cites work: Q4083487
cites work: Noise stability of functions with low influences: invariance and optimality
cites work: On the critical percolation probabilities
cites work: An approximate zero-one law
cites work: On Russo's approximate zero-one law
DOI: 10.4007/ANNALS.2012.176.1.9
Recommended article: On the structure of Boolean functions with small spectral norm
Recommended article: The Fourier Entropy–Influence Conjecture for Certain Classes of Boolean Functions
Recommended article: Approximation of biased Boolean functions of small total influence by DNFs
Recommended article: On the complexity of Boolean functions with small number of ones
Recommended article: Boolean functions with small spectral norm, revisited
Recommended article: Q4418661
Recommended article: On the Power of Choice for Boolean Functions
Recommended article: Boolean functions with small spectral norm
Recommended article: A lower bound for the affinity level for almost all Boolean functions
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 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 \(\in…
description: scientific article; zbMATH DE number 6074020