Geodesic
Half-spaces with influential variable
Teoriâ veroâtnostej i ee primeneniâ, Tome 65 (2020) no. 1, pp. 142-150 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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
Mots-clés : influence. 
@article{TVP_2020_65_1_a8,
     author = {D. Dzindzalieta and F. G\"otze},
     title = {Half-spaces with influential variable},
     journal = {Teori\^a vero\^atnostej i ee primeneni\^a},
     pages = {142--150},
     year = {2020},
     volume = {65},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TVP_2020_65_1_a8/}
}
TY  - JOUR
AU  - D. Dzindzalieta
AU  - F. Götze
TI  - Half-spaces with influential variable
JO  - Teoriâ veroâtnostej i ee primeneniâ
PY  - 2020
SP  - 142
EP  - 150
VL  - 65
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/TVP_2020_65_1_a8/
LA  - ru
ID  - TVP_2020_65_1_a8
ER  - 
%0 Journal Article
%A D. Dzindzalieta
%A F. Götze
%T Half-spaces with influential variable
%J Teoriâ veroâtnostej i ee primeneniâ
%D 2020
%P 142-150
%V 65
%N 1
%U http://geodesic.mathdoc.fr/item/TVP_2020_65_1_a8/
%G ru
%F TVP_2020_65_1_a8
D. Dzindzalieta; F. Götze. Half-spaces with influential variable. Teoriâ veroâtnostej i ee primeneniâ, Tome 65 (2020) no. 1, pp. 142-150. http://geodesic.mathdoc.fr/item/TVP_2020_65_1_a8/

[1] M. Ben-Or, N. Linial, “Collective coin flipping”, Randomness and computation, Advances in Computing Research, 5, JAI Press, Greenwich, Conn., 1989, 91–115

[2] A. Ben-Tal, A. Nemirovski, C. Roos, “Robust solutions of uncertain quadratic and conic-quadratic problems”, SIAM J. Optim., 13:2 (2002), 535–560 | DOI | MR | Zbl

[3] V. K. Bentkus, D. Dzindzalieta, “A tight Gaussian bound for weighted sums of Rademacher random variables”, Bernoulli, 21:2 (2015), 1231–1237 | DOI | MR | Zbl

[4] H. D. Block, “The perceptron: a model for brain functioning. I”, Rev. Modern Phys., 34:1 (1962), 123–135 | DOI | MR | Zbl

[5] N. Cristianini, J. Shawe-Taylor, An introduction to support vector machines and other kernel-based learning methods, Cambridge Univ. Press, Cambridge, 2000, xiii+189 pp. | DOI | Zbl

[6] D. Dzindzalieta, “A note on random signs”, Lith. Math. J., 54:4 (2014), 403–408 | DOI | MR | Zbl

[7] A. Fiat, D. Pechyony, “Decision trees: more theoretical justification for practical algorithms”, Algorithmic learning theory, Lecture Notes in Comput. Sci., 3244, Lecture Notes in Artificial Intelligence, Springer, Berlin, 2004, 156–170 | DOI | MR | Zbl

[8] O. Friedland, O. Guédon, “Random embedding of $l_p^n$ into $l_r^{N}$”, Math. Ann., 350:4 (2011), 953–972 | DOI | MR | Zbl

[9] O. Goldreich, S. Goldwasser, D. Ron, “Property testing and its connection to learning and approximation”, J. ACM, 45:4 (1998), 653–750 | DOI | MR | Zbl

[10] R. K. Guy, “Any answers anent these analytical enigmas?”, Amer. Math. Monthly, 93:4 (1986), 279–281 | DOI | MR

[11] A. Hajnal, W. Maass, P. Pudlák, M. Szegedy, G. Turán, “Threshold circuits of bounded depth”, J. Comput. System Sci., 46:2 (1993), 129–154 | DOI | MR | Zbl

[12] J.-B. Hiriart-Urruty, “A new series of conjectures and open questions in optimization and matrix analysis”, ESAIM Control Optim. Calc. Var., 15:2 (2009), 454–470 | DOI | MR | Zbl

[13] R. Holzman, D. J. Kleitman, “On the product of sign vectors and unit vectors”, Combinatorica, 12:3 (1992), 303–316 | DOI | MR | Zbl

[14] J. Kahn, G. Kalai, N. Linial, “The influence of variables on boolean functions”, SFCS '88 Proceedings of the 29th annual IEEE symposium on Foundations of computer science (White Plains, NY, 1988), IEEE Comput. Soc. Press, Los Alamitos, CA, 1988, 68–80 | DOI

[15] S. Khot, G. Kindler, E. Mossel, R. O'Donnell, “Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?”, SIAM J. Comput., 37:1 (2007), 319–357 | DOI | MR | Zbl

[16] T. W. Körner, Fourier analysis, 2nd ed., Cambridge Univ. Press, Cambridge, 1989, xii+591 pp. | MR | Zbl

[17] A. E. Litvak, A. Pajor, M. Rudelson, N. Tomczak-Jaegermann, “Smallest singular value of random matrices and geometry of random polytopes”, Adv. Math., 195:2 (2005), 491–523 | DOI | MR | Zbl

[18] K. Matulef, R. O'Donnell, R. Rubinfeld, R. A. Servedio, “Testing halfspaces”, SIAM J. Comput., 39:5 (2010), 2004–2047 | DOI | MR | Zbl

[19] K. M. Matulef, Testing and learning Boolean functions, PhD thesis, Massachusetts Institute of Technology, 2009 | MR

[20] M. L. Minsky, S. A. Papert, Perceptrons. An introduction to computational geometry, expanded ed., The MIT Press, Cambridge, Mass.–London, 1988, xvi+292 pp. | Zbl

[21] A. B. J. Novikoff, On convergence proofs for perceptrons, Tech. rep., DTIC Doc., 1963

[22] R. O'Donnell, “Some topics in analysis of Boolean functions”, STOC '08 Proceedings of the 40th annual ACM symposium on Theory of computing (Victoria, 2008), ACM, New York, 2008, 569–578 | DOI | MR | Zbl

[23] R. Rubinfeld, M. Sudan, “Robust characterizations of polynomials with applications to program testing”, SIAM J. Comput., 25:2 (1996), 252–271 | DOI | MR | Zbl

[24] M. Rudelson, R. Vershynin, “Smallest singular value of a random rectangular matrix”, Comm. Pure Appl. Math., 62:12 (2009), 1707–1739 | DOI | MR | Zbl

[25] I. G. Shevtsova, “Ob absolyutnykh konstantakh v neravenstve Berri–Esseena i ego strukturnykh i neravnomernykh utochneniyakh”, Inform. i ee primen., 7:1 (2013), 124–125

[26] I. S. Tyurin, “A refinement of the remainder in the Lyapunov theorem”, Theory Probab. Appl., 56:4 (2011), 693–696 | DOI | DOI | MR | Zbl

[27] A. C.-C. Yao, “On ACC and threshold circuits”, SFCS '90 Proceedings of the 31st annual symposium on Foundations of computer science (St. Louis, MO, 1990), IEEE Comput. Soc. Press, Los Alamitos, CA, 1990, 619–627 | DOI | MR