Combinatorics: Ohad Klein, BIU, "Biased halfspaces, noise sensitivity, and local Chernoff inequalities"

Speaker: Ohad Klein, BIU
Title: Biased halfspaces, noise sensitivity, and local Chernoff inequalities
Let X be a random variable defined by X=\sum_i a_i x_i where x_i are independent random variables uniformly distributed in \{-1, 1\}, and a_i in R, the reals. Assume Var(X)=1=sum a_{i}^2. We investigate the tail behavior of the variable X, and apply the results to study halfspace functions f:{-1,1}^{n}-->{-1,1} defined by f(x)=1 (\sum_i a_i x_i > t) for some t in R.
A puzzle: Let a = max_{i} |a_{i}|. Is it true that Pr[|X| \leq a] \geq a/10?
Joint work with Nathan Keller.


Mon, 05/11/2018 - 11:00 to 13:00


Rothberg CS bldg, room B500, Safra campus, Givat Ram