This chapter is devoted to linear threshold functions, their generalization to higher degrees, and their exemplar the majority function. The study of LTFs leads naturally to the introduction of the Central Limit Theorem and Gaussian random variables — important tools in analysis of boolean functions. We will first use these tools to analyze the Fourier spectrum of the $\mathrm{Maj}_n$ function, which in some sense “converges” as $n \to \infty$. We’ll then extend to analyzing the degree-$1$ Fourier weight, noise stability, and total influence of general linear threshold functions.

## Leave a Reply