Biased halfspaces, noise sensitivity, and local Chernoff inequalities

Nathan Keller, Ohad Klein

A halfspace is a function $f:\{-1,1{\}}^n\to \{0,1\}$ of the form $f(x)=1(a\cdot x>t)$, where ${\sum }_i{a}_i^2=1$. We show that if $f$ is a halfspace with $\mathb…