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

The influence of the $k$’th coordinate on a Boolean function $f:{0,1}^n \rightarrow {0,1}$istheprobabilitythatflipping$x_k$changesthevalue$f(x)$\mathrm{.}Thetotalinfluence$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$canbe$\epsilon \mu$-approximated by a DNF of size $2^{2^{O(M\mathrm{/}ϵ)}}$. The dependence on $M$ is sharp up to the constant factor in the double exponent.