Combinatorics: Nathan Keller (BIU)

Title:   Local tail inequalities, biased halfspaces, and noise sensitivity


Weighted sums of Rademacher random variables (namely, X=\sum a_i x_i, where \sum a_i^2 = 1 and {x_i} are i.i.d. random variables such that Pr[x_i=1]=Pr[x_i=-1]=1/2), were studied extensively. Local tail inequalities for such variables compare the tail probabilities Pr[X>t] and  Pr[X>t+delta]. An example is the following inequality (Devroye & Lugosi, 2008): If Pr[X>t]=epsilon, then  Pr[X>t+delta]<epsilon/2  holds for delta<=c/sqrt{log(1/epsilon)}, where  c  is a universal constant.

We present new inequalities of this type and apply them to obtain results on biased (Boolean) halfspaces, noise sensitivity of Boolean functions, and correlation inequalities. In particular, we determine the exact asymptotic order of the first-level Fourier weight and of the maximal influence of a Boolean halfspace  1{\sum a_i x_i>t}, providing a sharp generalization of theorems of Matulef, O'Donnell, Rubinfeld, and Servedio. We discuss possible extensions and applications of our methods.

Joint work with Ohad Klein.


Mon, 01/06/2020 - 11:00 to 13:00