The influence of the $k$'th coordinate on a Boolean function $f:\{0,1\}^n \rightarrow \{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) \leq 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) \geq 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) \leq 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.

Thanks. We have received your report. If we find this content to be in
violation of our guidelines,
we will remove it.

Ok