Analytic Methods in Theoretical Computer Science and Combinatorics
Analytic Methods in Theoretical Computer Science and Combinatorics
(Masters and PhD Students, Summer 2024)
(Masters and PhD Students, Summer 2024)
Instructor Arijit Ghosh
Status Ongoing
Teaching assistant Swarnalipa Dutta
Description Introduction to Discrete Fourier Analysis and its applications in Theoretical Computer Science and Combinatorics
Prerequisites Mathematical maturity of a finishing undergraduate student in mathematical sciences
Class timings Tuesdays and Fridays from 2:00 pm to 4:00 pm
Syllabus
Discrete Fourier Analysis
Influence
Noise Sensitivity
Polynomial Approximations
Random Restrictions
Hypercontractivity
Invariance Principle
Applications in
Social Choice Theory
Property Testing and Learning Theory
Circuit Complexity
Cryptography
Extremal Combinatorics
Pseudorandomness
Hardness of Approximation and PCP Theorem
Additive Combinatorics
Random Graph Theory
Recent important results
Proof of Sensitivity Conjecture
Resolution of Kahn-Kalai Conjecture
Improved Sunflower Lemma
Recent advancements in the three-term arithmetic progression-free set problem
References
[MU05] Michael Mitzenmacher and Eli Upfal, Probability and Computing, Cambridge University Press, 2005
[B24] Thomas Bloom, Density Increment Methods in Additive Combinatorics, Course notes, University of Oxford, 2024
[B21] Thomas Bloom, Additive Combinatorics, Course notes, University of Oxford, 2021
[HHL19] Hamed Hatami, Pooya Hatami, and Shachar Lovett, Higher-order Fourier Analysis and Applications, Foundations and Trends in Theoretical Computer Science, 2019
[M24] Dor Minzer, Topics in Combinatorics: Analysis of Boolean Functions, Course Notes, MIT, 2024
[MR95] Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, 1995
[O12] Ryan O'Donnell, Analysis of Boolean Functions, Course Notes, CMU, 2012
[O14] Ryan O'Donnell, Analysis of Boolean Functions, Cambridge University Press, 2014
[T23] Avishay Tal, Analysis of Boolean Functions, Course Notes, UC Berkeley, 2023
[V12] Salil P. Vadhan, Pseudorandomness, Foundations and Trends in Theoretical Computer Science, 2012
[WS11] David P. Williamson and David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011
[W08] Ronald de Wolf, A Brief Introduction to Fourier Analysis, Graduate Surveys, Theory of Computing, 2008
Lecture details
Topics covered in Lecture 1
Introduction to the course
Boolean functions
Space of real-valued functions over the Hamming/Boolean cube
Multilinear polynomials
Fourier analysis of real-valued functions over the Hamming/Boolean cube
Basic Fourier facts
Reading materials:
Topics covered in Lecture 2
Facts about the dual group of characters and its isomorphism
Introduction to property testing
Testing if a Boolean function is a constant
Definition of a linear function and its robust variants
Linearity Testing and BLR test
Reading materials:
Topics covered in Lecture 3
Continuation of BLR test analysis from previous class
Properties of Fourier coefficients of Boolean functions
Modified BLR test for testing affine functions
Bent function and its Fourier coefficients
Establishing the limitation of testing higher degrees using Fourier analysis via Bent functions
Convolution and its properties
Reading materials:
Topics covered in Lecture 4
Different voting rules and their properties
Majority, AND/OR, Dictatorship, and k-junta
Linear Threshold Function (LTF)
Tribes
Properties of voting functions
Monotone
Symmetric
Odd function
Transitive-symmetric
Unanimous
Reading materials:
Chapter 2 from [O14]
Topics covered in Lecture 5
Sensitive/pivotal coordinate of a function at a point
Influence of a coordinate
Compute influence of Majority function
Effect of a coordinate and its relation to Fourier coefficients
Reading materials:
Chapter 2 from [O14]