Computer Science/Discrete Mathematics Seminar II | |

Topic: | Fourier tails for Boolean functions and their applications |

Speaker: | Avishay Tal |

Affiliation: | Member, School of Mathematics |

Date: | Tuesday, May 3 |

Time/Room: | 10:30am - 12:30pm/S-101 |

Video Link: | https://video.ias.edu/csdm/2016/0503-Tal |

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$.

We consider Boolean functions whose Fourier-tails have a threshold behavior. That is, above some level $t$, the tails decrease exponentially fast. Several weak classes of Boolean functions have exponentially small Fourier tails:

- width-w DNFs,

- small-depth circuits,

- small-size de-Morgan formulas, and

- small-sensitivity Boolean functions