zbMATH — the first resource for mathematics

Boolean functions with low average sensitivity depend on few coordinates. (English) Zbl 0909.06008
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.

MSC:
 06E30 Boolean functions 28A35 Measures and integrals in product spaces
Full Text: