HALF-SPACES WITH INFLUENTIAL VARIABLE

Dzindzalieta D, Götze F (2020)
THEORY OF PROBABILITY AND ITS APPLICATIONS 65(1): 114-120.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Autor*in
Dzindzalieta, D.; Götze, FriedrichUniBi
Abstract / Bemerkung
We consider Boolean functions f defined on Boolean cube {-1, 1}(n) of half-spaces, i.e., functions of the form f (x) = sign(omega.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 parallel to omega parallel to(2 )<= 1 and parallel to omega parallel to(infinity) = delta for some delta > 0. Let 0 <= epsilon <= 1 be such that vertical bar Ef vertical bar <= 1 - epsilon. We prove that there exists a constant C > 0 such that max,(Inf(i),f) >= C delta epsilon, where Inf(i) f denotes the influence of the ith 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-root 2/64 approximate to 0.066. As an auxiliary result we prove a lower bound for small ball inequalities of linear combinations of Rademacher random variables.
Stichworte
Boolean functions; small ball inequalities; linear threshold functions; Boolean cube; influence
Erscheinungsjahr
2020
Zeitschriftentitel
THEORY OF PROBABILITY AND ITS APPLICATIONS
Band
65
Ausgabe
1
Seite(n)
114-120
ISSN
0040-585X
eISSN
1095-7219
Page URI
https://pub.uni-bielefeld.de/record/2945467

Zitieren

Dzindzalieta D, Götze F. HALF-SPACES WITH INFLUENTIAL VARIABLE. THEORY OF PROBABILITY AND ITS APPLICATIONS. 2020;65(1):114-120.
Dzindzalieta, D., & Götze, F. (2020). HALF-SPACES WITH INFLUENTIAL VARIABLE. THEORY OF PROBABILITY AND ITS APPLICATIONS, 65(1), 114-120. doi:10.1137/S0040585X97T989866
Dzindzalieta, D., and Götze, F. (2020). HALF-SPACES WITH INFLUENTIAL VARIABLE. THEORY OF PROBABILITY AND ITS APPLICATIONS 65, 114-120.
Dzindzalieta, D., & Götze, F., 2020. HALF-SPACES WITH INFLUENTIAL VARIABLE. THEORY OF PROBABILITY AND ITS APPLICATIONS, 65(1), p 114-120.
D. Dzindzalieta and F. Götze, “HALF-SPACES WITH INFLUENTIAL VARIABLE”, THEORY OF PROBABILITY AND ITS APPLICATIONS, vol. 65, 2020, pp. 114-120.
Dzindzalieta, D., Götze, F.: HALF-SPACES WITH INFLUENTIAL VARIABLE. THEORY OF PROBABILITY AND ITS APPLICATIONS. 65, 114-120 (2020).
Dzindzalieta, D., and Götze, Friedrich. “HALF-SPACES WITH INFLUENTIAL VARIABLE”. THEORY OF PROBABILITY AND ITS APPLICATIONS 65.1 (2020): 114-120.

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®

Suchen in

Google Scholar