check
Combinatorics: Ohad Klein, BIU, "Biased halfspaces, noise sensitivity, and local Chernoff inequalities" | Einstein Institute of Mathematics

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

Date: 
Mon, 05/11/201811:00-13:00
Location: 
Rothberg CS bldg, room B500, Safra campus, Givat Ram
Speaker: Ohad Klein, BIU
Title: Biased halfspaces, noise sensitivity, and local Chernoff inequalities
Abstract:
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.