Chapter 5: Majority and threshold functions

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




You can use most standard LaTeX, as well as these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>