Biased halfspaces, noise sensitivity, and local Chernoff inequalities

Biased halfspaces, noise sensitivity, and local Chernoff inequalities, Discrete Analysis 2019:13, 50 pp.

A Boolean function is a function from the discrete cube, which it is convenient to represent as $\{-1,1\}^n$, to $\{0,1\}$. For obvious reasons, Boolean functions are a basic object of study in theoretical computer science, and a major strand of that study concerns analytic results about them, and in particular about the behaviour of their Fourier transforms.

An important class of Boolean functions is that of halfspaces, also known as linear threshold functions which are (characteristic functions of) sets of the form $\{x\in\{-1,1\}^n:\sum_ia_ix_i>t\}$, where the coefficients $a_i$ are real numbers such that $\sum_ia_i^2=1$. Although such functions might seem quite simple, the fact that the linearity is over $\mathbb R$ rather than $\mathbb F_2$ means that the Fourier analysis of such functions is not completely straightforward: in fact, it raises interesting and important questions.

If $t=0$ and the coefficients are such that no $\pm 1$ sum of them is zero, then the density of the halfspace, or the expectation of the corresponding function, is 1/2. Such halfspaces are called unbiased, and they have been the ones that have been most studied. However, biased halfspaces arise naturally in certain applications, and the purpose of this paper is to obtain similar results for them as well.

One of the main results of the paper concerns the degree-1 Fourier weight of a halfspace. This is defined to be the sum of the squares of the Fourier coefficients of characters corresponding to singletons. Given a function $f$, these Fourier coefficients are $\hat f({i})=\mathbb E_xf(x)x_i$, for $i=1,2,\dots,n$. They are important, because it has been shown that if $f$ is a halfspace, then it is completely determined by these coefficients. (In the biased case one must also take into account the coefficient $\hat f(\emptyset)=\mathbb E_xf(x)$.)

In the unbiased case, it is known that a significant fraction of the $L_2$-norm of $\hat f$ is accounted for by the level-1 Fourier coefficients: the degree-1 Fourier weight of $f$ is always at least 1/8. In the biased case, if we know that $f$ has density $\epsilon$, then $\|f-\mathbb Ef\|_2^2=\epsilon(1-\epsilon)^2+(1-\epsilon)\epsilon^2=\epsilon(1-\epsilon)$, which by Parseval gives us a trivial upper bound for the degree-1 Fourier weight (trivial because it makes no use of the fact that $f$ is a halfspace). However, a much better upper bound of $2\epsilon^2\log(1/\epsilon)$ has been shown: it is known as the level-1 inequality. Thus, a reasonable analogue of the result in the biased case would be the statement that the level-1 inequality is sharp up to a constant.

This was proved by Matulef, O’Donnell, Rubinfeld and Servedio under the additional hypothesis that all the coefficients $a_i$ are small – such halfspaces are often called smooth, but Kalai, Keller and Mossel conjectured that it should hold for all halfspaces. That conjecture is proved in this paper, as well as other results of a similar flavour, one of which is an “inverse theorem” that shows that any Boolean function for which the level-1 weight is within a constant of the maximum is correlated with a halfspace.

An interesting feature of the paper is the method it uses. Previous results often applied only for smooth halfspaces, for which the so-called invariance principle could be brought to bear, which allows one to approximate the function by a Gaussian. That is of course not possible in general: to obtain results for arbitrary halfspaces, the authors decompose the coefficients into “large” and “small” and apply a new large deviation bound, which is closely related to a "local Chernoff bound” of Devroye and Lugosi but has a completely different proof.