Boolean functions with low average sensitivity depend on few coordinates (Q1280280)

The main topic is the approximation of a Boolean function \(f:\{0,1\}^n\to \{0,1\}\) by a function \(g\) depending on only a few coordinates \(i_1,\dots,i_m\), i.e. we always have \(g(x_1,\dots,x_n)=g(x_1',\dots,x_n')\) if \(x_{i_j}=x_{i_j}'\) for each index \(j\). Approximation means that the probability of \(f=g\) is large. The author introduces the sensitivity of a point \(v\in\{0,1\}^n\), which is the number of points \(v'\in\{0,1\}^n\) with \(f(v')\neq f(v)\) that differ from \(v\) in exactly one coordinate. The average sensitivity of \(f\) is the average of the sensitivities of all points in \(\{0,1\}^n\). A related concept is that of influence: The influence of the coordinate \(i\) with respect to a probability measure \(\mu\) on \(\{0,1\}^n\) is the \(\mu\)-probability of \(f(x_1,\dots,x_{i-1},0,x_{i+1},\dots,x_n)\neq f(x_1,\dots,x_{i-1},1,x_{i+1}, \dots,x_n)\) by choosing \(x_1,\dots,x_{i-1},x_{i+1},\dots,x_n\) randomly. Let \(\text{av}_\mu(f)\) denote the sum of the influences of all coordinates. Then the average sensitivity of \(f\) is \(\text{av}_\mu(f)\) where \(\mu\) is the uniform measure on \(\{0,1\}^n\) (i.e. \(\mu (\{v\})=2^{-n}\) for each point \(v\in \{0,1\}^n)\). For \(0<p<1\), define the measure \(\mu_p\) by \(\mu_p(\{v\})=p^{| v| }(1-p)^{n-| v| }\) for each \(v \in \{0,1\}^n\) (\(| v| \) is the number of ones in \(v\)). It is proved that \(f\) can be approximated by a function depending on only a few variables if \(\text{av}_{\mu_p}(f)\) is small. More precisely: There exists a constant \(c>0\) (only depending on \(p\)) such that for each function \(f:\{0,1\}^n\to \{0,1\}\) and \(\varepsilon >0\), there is a function \(g:\{0,1\}^n\to \{0,1\}\) depending on at most \(c^{\text{av}_{\mu_p}(f)/\varepsilon}\) coordinates such that the \(\mu_p\)-probability of \(f\neq g\) is at most \(\varepsilon\). For the uniform measure (i.e. for \(p=1/2\)), an upper bound for the number of coordinates is explicitly given and its tightness is discussed.