Fourier Analysis on the Boolean Cube and its Applications (Jan.-Feb. 2020)

Description Brief introduction to Fourier Analysis on the Boolean Cube, and its Applications in Theoretical Computer Science and Combinatorics.

Instructors Arijit Ghosh

Lecture details

Topics covered in Lecture 1

• Introduction to the course

• Discussion on the cap set problem and testability of almost linear functions

• Multilinear polynomials and Fourier Analysis on the Boolean Cube

• Simple properties of Fourier expansion

• References:

  • • Sections 1.1 to 1.4 of Chapter 1 from the book [D14]

    • Section 2 from the survey [W08]

Topics covered in Lectures 2 and 3

• Introduction to Fourier Analysis on finite Abelian Groups

• Capset problem and Meshulam's upper bound on capsets

• References:

  • • Sections 2.5 and 3.1 from [L17]

Topics covered in Lecture 4

• Linearity testing and BLR test

• BLR test for affine linearity

• References:

  • • Chapter 2 from [LH20]

Topics covered in Lecture 5 (Guest lecture by Manaswi Paraashar)

• Complexity measures for Boolean functions

• Degree and approximate degree

• Sensitivity, block sensitivity, and average sensitivity

• Influence

• Fourier entropy

• Relations between different complexity measures

• Sensitivity conjecture

• Fourier entropy-influence conjecture

• References:

  • • Chapters 1 and 2 from [D14]

    • See the survey [BW02]

• Additional references:

  • • For approximate degree see [NS94]

    • Recent proof of sensitivity conjecture see [H19]

    • More recent development on the sensitivity conjecture [LNS20]

    • Read Gil Kalai's blog on Fourier entropy-influence conjecture