## Fourier tails for Boolean functions and their applications

Avishay Tal

Member, School of Mathematics

May 3, 2016

The discrete Fourier transform is a widely used tool in the analysis of Boolean functions. One can view the Fourier transform of a Boolean function $f:\{0,1\}^n \to \{0,1\}$ as a distribution over sets $S \subseteq [n]$. The Fourier-tail at level $k$ is the probability of sampling a set $S$ of size at least $k$.