Probability and Stochastic Processes Seminar

Probability and Stochastic Processes Seminar

Ohad Klein


Bar-Ilan University

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 are real numbers. We investigate the tail behavior of the variable X, and apply the results to study associated linear threshold functions f:{-1,1}^n→{0,1}, which are indicators of events of the form {sum a_i x_i > t} for real numbers t. A puzzle: Let a = max_i |a_i| and assume sum a_i^2 = 1. Is it true that Pr[|X| <= a] > a/10 ?   Joint work with Nathan Keller.  

Date: Tue 21 Jan 2020

Start Time: 11:30

End Time: 12:30

861 | Electrical Eng. Building