Half-spaces with influential variable

D. Dzindzalieta ; F. Götze

Teoriâ veroâtnostej i ee primeneniâ, Tome 65 (2020) no. 1, pp. 142-150

Résumé

We consider Boolean functions $f$ defined on Boolean cube $\{-1,1\}^n$ of half-spaces, i.e., functions of the form $f(x)=\operatorname{sign}(\omega\cdot x-\theta)$. Half-space functions are often called linear threshold functions. We assume that the Boolean cube $\{-1,1\}^n$ is equipped with a uniform measure. We also assume that $\|\omega\|_2\leq 1$ and $\|\omega\|_{\infty} = \delta$ for some $\delta>0$. Let $0\leq\varepsilon\leq 1$ be such that $|\mathbf{E} f|\leq 1-\varepsilon$. We prove that there exists a constant $C>0$ such that $\max_i(\operatorname{Inf}_i f)\geq C\delta\varepsilon$, where $\operatorname{Inf}_i f$ denotes the influence of the $i$th coordinate of the function $f$. This establishes the lower bound obtained earlier by Matulef et al. [SIAM J. Comput., 39 (2010), pp. 2004–2047]. We also show that the optimal constant in this inequality exceeds $3\sqrt{2}/64\approx 0.066$. As an auxiliary result we prove a lower bound for small ball inequalities of linear combinations of Rademacher random variables.

Détail

Keywords: Boolean functions, small ball inequalities, linear threshold functions, Boolean cube
Mots-clés : influence.