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:
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:
Additional references: