This article is cited in 1 paper

Short Communications

Half-spaces with influential variable

D. Dzindzalieta^a, F. Götze<sup>b

a</sup> Institute of Data Science and Digital Technologies, Faculty of Mathematics and Informatics, Vilnius University
^b Fakultät für Mathematik, Universität Bielefeld, Bielefeld, Germany

Abstract: 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.

Keywords: Boolean functions, small ball inequalities, linear threshold functions, Boolean cube, influence.

Received: 04.08.2015
Revised: 15.05.2019

DOI: 10.4213/tvp5219

 English version: Theory of Probability and its Applications, 2020, 65:1, 114–120

Bibliographic databases:

• 
• 
•