Introduction to Fourier Analysis of Boolean Functions

Project Description

The project involved learning about the Fourier Analysis of Boolean Functions. The mentees learnt about the boolean functions and their representation. They learnt about the Fourier expansion of Boolean Functions. They also saw some Fourier identities of Boolean functions. It also involved some concepts of finite vector spaces which was new to all the mentees. It then discussed the Fourier Span and Dimension of a function. Introduced a problem that establishes an inequality between the two. Finished out with a lemma that directly relates to results close to this problem.

Mentors

• Mohd Talib Siddiqui - 180426

Learning Roadmap

The first few basic topics were covered by a book on Boolean functions. Later, a summary of the basic topics were given in a form of report prepared by me. For the final lemma of the project, a reference to a paper was provided. Slides prepared by me were also supplied to the mentees on the lemma.

Resources

Analysis Of Boolean Functions - Ryan O’Donnell Fourier sparsity, spectral norm, and the Log-rank conjecture - Hing Yin Tsang, Chung Hoi Wong, Ning Xie, Shengyu Zhang (Lemma 30)