Theory Seminar: A Structure Theorem for Biased Boolean Functions with A Small Total Influence

Nathan Keller (Bar-Ilan University)

Wednesday, 22.11.2017, 12:30

Taub 201

The influence of the k'th coordinate on a Boolean function f:{0,1}^n -> {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 classical `Junta Theorem' of Friedgut (1998) asserts that if I(f) <= 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) >= 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) <= 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 a constant factor.

Joint work with Noam Lifshitz.

For a biased function with E[f]=\mu, the edge isoperimetric inequality on the cube implies that I(f) >= 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) <= 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 a constant factor.

Joint work with Noam Lifshitz.