Approximation of biased Boolean functions of small total influence by DNF's

Abstract

The influence of the $k$'th coordinate on a Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ is the probability that flipping $x_k$ changes the value $f(x)$. The total influence $I(f)$ is the sum of influences of the coordinates. The well-known `Junta Theorem' of Friedgut (1998) asserts that if $I(f)\le M$, then $f$ can be $\epsilon$-approximated by a function that depends on $O(2^{M/\epsilon })$ coordinates. Friedgut's theorem has a wide variety of applications in mathematics and theoretical computer science. For a biased function with $E[f]=\mu$, the edge isoperimetric inequality on the cube implies that $I(f)\ge 2\mu \log (1/\mu )$. Kahn and Kalai (2006) asked, in the spirit of the Junta theorem, whether any $f$ such that $I(f)$ is within a constant factor of the minimum, can be $\epsilon \mu$-approximated by a DNF of a `small' size (i.e., a union of a small number of sub-cubes). We answer the question by proving the following structure theorem: If $I(f)\le 2\mu (\log (1/\mu )+M)$, then $f$ can be $\epsilon \mu$-approximated by a DNF of size $2^{2^{O(M/\epsilon )}}$. The dependence on $M$ is sharp up to the constant factor in the double exponent.

14 pages