Stability of Linear Threshold Functions

Boolean Half-spaces or Linear Threshold Functions (LTFs) are an important class of Boolean functions which come up in Learning Theory (Perceptrons), Social Choice Theory etc.. We will study lower bounds on the stability of LTFs. Firstly, we look at the problem of finding the best lower bound for the total level-0 and level-1 weight of LTFs, denoted by W1[LTF], which is conjectured to be 2/π. We will present the well-known bound of W1[LTF] ≥1/2 [GL94], and then look at some recent progress [DDS12] which shows that W1[LTF] ≥ 1/2 + c for some c > 0.

We then look at a stronger conjecture from [BKS98] which claims that Majority is the least stable among all LTFs on n(odd) variables. We give a counter example to this conjecture. We make a new conjecture that for any LTF f, Stab_ρ[f] ≥ (2/π) arcsin ρ ∀ρ ∈ [0, 1] and then give evidence for this new conjecture.