Halfspaces with influential variable

В этой статье рассматриваются булевы функции $f$, определенные на гиперкубе $\{-1,1\}^n$ полупространств, т.е. функции вида $f(x)=\operatorname{sign}(\omega\cdot x-\theta)$. В литературе такие функции также известны как линейные пороговые функции. Предположим, что гиперкуб $\{-1,1\}^n$ наделен равномерным распределением. Предположим далее, что $\|\omega\|_2\leq 1$ и $\|\omega\|_{\infty} = \delta$ для какого-либо $\delta>0$. Пусть $0\leq\varepsilon\leq 1$ будет такое число, что $|\mathbf{E} f|\leq 1-\varepsilon$. В этой работе доказывается, что существует постоянная $C>0$ такая, что $\max_i(\operatorname{Inf}_i f)\geq C\delta\varepsilon$, где $\operatorname{Inf}_i f$ обозначает влияние координаты $i$ функции $f$. Это устанавливает нижнюю оценку, которая была предположена в работе [18]. Также доказано, что оптимальная константа в этом неравенстве превосходит $3\sqrt{2}/64\approx 0.066$. В качестве вспомогательного результата мы даем нижнюю оценку для малых уклонений линейных комбинаций случайных величин Радемахерa.