Program Overview

Analysis of Boolean Functions - Monsoon Semester

Course Details

The course "Analysis of Boolean Functions" is offered during the monsoon semester. The classes are scheduled on Mondays from 11:30-13:00 and Wednesdays from 14:00-15:30 in location A201. The instructor for the course is Prahladh Harsha.

Problem Sets

The following problem sets are assigned:

1. Problem Set 1 (out: 11 Sep, due: 27 Sep)
2. Problem Set 2 (out: 27 Sep, due: 16 Oct)
3. Problem Set 3 (out: 6 Nov, due: 20 Nov)
4. Problem Set 4 (out: 22 Nov, due: 6 Dec)

Lectures

The lecture schedule is as follows:

• 4 Sep: Introduction to Analysis of Boolean Functions
• 6 Sep: Fourier Expansion and Linearity testing
• 11 Sep: Hastad's 3-bit PCPs - Part I
• 13 Sep: Hastad's 3-bit PCPs - Part II
• 18 Sep: Voting theory and Social Choice
• 20 Sep: Voting theory and spectral concentration
• 25 Sep: Spectral concentration and learning
• 27 Sep: Goldreich-Levin theorem
• 2 Oct: No class (Gandhi Jayanthi)
• 4 Oct: Learning Decision Trees and DNFs
• 9 Oct: Learning AC0 functions
• 11 Oct: Hardness Amplification: Hardcore set lemma
• 16 Oct: Hardness Amplification within NP
• 18 Oct: Majority, LTFs and PTFs
• 23 Oct: Noise Stability of Majority
• 25 Oct: Introduction to Hypercontractivity
• 30 Oct: Hypercontractivity and FKN Theorem
• 1 Nov: No class
• 6 Nov: Small set expansion of noisy hypercube
• 8 Nov: Kahn-Kalai-Linial Theorem
• 13 Nov: Fourier on the p-biased hypercube
• 15 Nov: p-biased Erdos-Ko-Rado Theorem
• 16 Nov: (2-)-hardness of approximating Vertex Cover
• 20 Nov: The Hypercontractivity theorem for hypercube
• 22 Nov: Gaussian Space
• 23 Nov: The Berry-Esseen Theorem
• 27 Nov: Invariance Principle
• 29 Nov: Majority is Stablest Theorem
• 1 Dec: Roth's Theorem: 3-APs in Z

Tentative Schedule for Future Lectures

• Other topics (open questions?) (2 lectures)
• 6 Dec: pset 4 due, pset 5 out

References

1. [Fil] A course on Boolean Function Analysis (offered by Yuval Filmus) at Technion
2. [Har] A course on PCPs (offered by Prahladh Harsha) at TIFR and IMSc
3. [HVV] Alexander Healy, Salil P. Vadhan, Emanuele Viola: Using Nondeterminism to Amplify Hardness
4. [Kop] A course on topics in Complexity and Pseudorandomness (offered by Swastik Kopparty) at Rutgers University
5. [vMe] A course on Complexity Theory (offered by Dieter van Melkebeek) at University of Wisconsin-Madison
6. [O'D1] A course on Boolean Function Analysis (offered by Ryan O'Donnell) at CMU
7. [O'D2] Ryan O'Donnell, "Analysis of Boolean Functions", Cambridge University Press, 2014
8. [O'D3] A course on Boolean Function Analysis (offered by Ryan O'Donnell) at CMU
9. [Tre] A course on graph partitioning and expansion (offered by Luca Trevisan) at Stanford

Requirements

Students taking the course for credit are expected to:

• Attend lectures
• Do problem sets (approximately 1 pset every 2.5 weeks)
• Give a presentation