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

References

  • [D14] Ryan O'Donnell: Analysis of Boolean Functions, Cambridge University Press, 2014.

  • [W08] Ronald de Wolf: A Brief Introduction to Fourier Analysis on the Boolean Cube, Theory of Computing, Graduate Surveys, 2008.

  • [L17] Shachar Lovett: Additive Combinatorics and its Applications in Theoretical Computer Science, Theory of Computing, Graduate Surveys, 2017.

  • [LH20] Shachar Lovett, Hamed Hatami and Pooya Hatami: Higher-order Fourier Analysis and Applications, Foundations and Trends in Theoretical Computer Science, 2020.

  • [NS94] Noam Nisan and Mario Szegedy: On the Degree of Boolean Functions as Real Polynomials. Computational Complexity, 4: 301-313, 1994.

  • [H19] Hao Huang: Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture, Annals of Mathematics, 190: 949-955, 2019.

  • [BW02] Harry Buhrman, Ronald de Wolf: Complexity measures and decision tree complexity: a survey, Theoretical Computer Science, 288(1): 21-43, 2002.

  • [LNS20] Sophie Laplante, Reza Naserasr, Anupa Sunny: Sensitivity lower bounds from linear dependencies. ECCC 27: 2, 2020.

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