Half-Spaces with Influential Variable
Dainius Dzindzalieta, Friedrich Götze · Theory of Probability and Its Applications · 2020
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.