## Analysis of Boolean Functions - Monsoon Semester (2017-18)

Time: Mon 11:30-13:00, Wed 14:00-15:30
Location: A201
Instructors :

#### Problem Sets

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

#### Lectures

 4 Sep 1. Introduction Administrivia, Introduction to Analysis of Boolean Functions, Overview of course Ref: [O'D1 (Lecture 1)] 6 Sep 2. Fourier Expansion and Linearity testing Ref: [Har (Lecture 6, Sec 6.1), O'D2 (Chap 1)] 11 Sep 3. Hastad's 3-bit PCPs - Part I Dictator Tests, Label Cover, Hardness of gap-LabelCover, a brief introduction to PCPs Ref: [Har (Lecture 11, Sec 11.1, 11.2 and 11.4)] 13 Sep 4. Hastad's 3-bit PCPs - Part II Long code, dictators, Hastad's MAX3LIN2 test Ref: [Har (Lecture 11, Sec 11.3 and 11.5)] 18 Sep 5. Voting theory and Social Choice Influence, noise stability, Condorcet's paradox, Arrow's theorem Ref: [O'D2 (Chap 2)] 20 Sep 6. Voting theory and spectral concentration Kalai's proof of Arrow's theorem; Spectral concentration and introduction to learning Ref: [O'D2 (Sec 2.5, 3.1, 3.4)] 25 Sep 7. Spectral concentration and learning Spectral concentration, relation to noise sensitivity, low-degree learning algorithm, decision trees Ref: [O'D2 (Sec 3.1, 3.2, 3.4)] 27 Sep 8. Goldreich-Levin theorem Kushilevitz-Mansour algorithm for Goldreich-Levin, learning with random and membership queries, DNFs Ref: [O'D2 (Sec 3.3, 3.4, 3.5, 4.1)] 2 Oct No class; Gandhi Jayanthi 4 Oct 9. Learning Decision Trees and DNFs Learning Decision trees, Random restrictions, Switching lemma, Mansour's algorithm for learning DNFs Ref: [O'D2 (Sec 4.3-4.4), O'D1 (Lectures 8,9,10)] 9 Oct 10. Learning AC0 functions LMN Theorem: Fourier concentration of AC0 circuits, Introduction to Hardness amplification Ref: [O'D2 (Sec 4.5), O'D1 (Lectures 10,17)] 11 Oct 11. Hardness Amplification: Hardcore set lemma Impagliazzo's hardcore set lemma, Yao's XOR Lemma Ref: [O'D1 (Lecture 17), Kop (Lecture 2), vMe (Lecture 14)] 16 Oct 12. Hardness Amplification within NP Hardness amplification of balanced functions, expected bias, noise sensitivity of Boolean functions Ref: [vMe (Lectures 14-15), O'D1 (Lecture 18), O'D3] 18 Oct 13. Majority, LTFs and PTFs Noise sensitivity of recursive majority; Introduction to LTFs and PTFs, Chow's theorem, Lower bound on level <=1 weight of LTFs, Peres' Theorem Ref: [vMe (Lectures 14-15), O'D1 (Lecture 18), O'D3, HVV, O'D2 (Sec 5.1 and 5.5)] 23 Oct 14. Noise Stability of Majority Peres' Theorem, Central limit theorem, Noise stability of Majority, Majority is least stable LTF conjecture, Gotsman-Linial conjecture for PTFs Ref: [ O'D2 (Sec 5.2 and 5.5), O'D1 (Lectures 19-20)] 25 Oct 15. Introduction to Hypercontractivity Fourier coefficients of Majority, Hypercontractivity, Bonami's lemma Ref: [O'D2 (Sec 5.3 and 9.1)] 30 Oct 16. Hypercontractivity and FKN Theorem Small ball probability of polynomial functions, Friedgut-Kalai-Naor Theorem, (2,4) and (4/3,2) hypercontractivity, small set expansion of noisy hypercube Ref: [O'D2 (Sec 9.1, 9.2, 9.5), O'D1 (Lectures 13)] 1 Nov No class 6 Nov 17. Small set expansion of noisy hypercube small sets of the hypercube are noise sensitive, noisy hypercube, eigen spectrum of Cayley graphs Ref: [O'D2 (Sec 9.2, 9.5), Tre (Lecture 6)] 8 Nov 18. Kahn-Kalai-Linial Theorem Weight-k inequalities, Kahn-Kalai-Linial theorem, Collective coin flipping, Friedgut's theorem Ref: [O'D2 (Sec 9.5-9.6), O'D1 (Lectures 14-15)] 13 Nov 19.Fourier on the p-biased hypercube Friedgut's theorem; Fourier analysis on general product domains, p-biased hypercube. Ref: [O'D2 (Sec 9.6, 8.4), Fil (Sec 3)] 15 Nov 20. p-biased Erdos-Ko-Rado Theorem Russo-Margulis Lemma, EKR Theorem on slice and p-biased hypercube, Hoffman bound, Friedgut's proof of EKR theorem Ref: [O'D2 (Sec 8.4), Fil (Sec 3)] 16 Nov 21. (2-ε)-hardness of approximating Vertex Cover Introduction to Unique Games, UG-hardness of approximating vertex cover Ref: [notes] 20 Nov 22. The Hypercontractivity theorem for hypercube Applications of hypercontractivity: tail bounds for polynomials; 2-function version of hypercontractivity, two-point inequality Ref: [O'D2 (Sec 9.3, 9.4, 10.1), O'D1 (Lecture 16)] 22 Nov 23. Gaussian Space Introduction to Gaussian space, noise operator, orthonormal of Hermite polynomials, Berry-Esseen theorem Ref: [O'D2 (Sec 11.1, 11.2, 11.5)] 23 Nov 24. The Berry-Esseen Theorem Proof of the Berry-Esseen Theorem via the Lindeberg replacement method (aka Hybrid argument) [O'D2 (Sec 11.5), O'D1 (Lecture 21)] 27 Nov 25. Invariance Principle Proof of the invariance principle; Approximability of MAXCUT, Goemans-Williamson algorithm Ref: [O'D2 (Sec 11.6), O'D1 (Lecture 22), Har (Lecture 2-3)] 29 Nov 26. Majority is Stablest Theorem KKMO reduction: MIS Theorem implies UG-hardness of MAXCUT, Borell's Theorem, Proof of MIS using Borell's Theorem and invariance principle. Ref: [notes, Har (Lecture 12), O'D2 (Sec 11.7), O'D3 (Lecture 20)] 1 Dec 27. Roth's Theorem: 3-APs in Z Ref: [notes]

#### Tentative schedule for Future Lectures

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

#### References

The links below point to the actual location of papers at the author's homepages or other electronic repositories and the papers are not reposted locally.

1. [Fil] A course on Boolean Function Analysis (offered by Yuval Filmus) at Technion: Analysis of Boolean Functions, Winter 2015-16.
2. [Har] A course on PCPs (offered by Prahladh Harsha) at TIFR and IMSc: Limits of approximation algorithsm: PCPs and Unique Games.
3. [HVV] Alexander Healy, Salil P. Vadhan, Emanuele Viola: Using Nondeterminism to Amplify Hardness. SIAM J. Comput. 35(4): 903-931 (2006). [DOI]
4. [Kop] A course on topics in Complexity and Pseudorandomness (offered by Swastik Kopparty) at Rutgers University: 198:676: Combinatorial Methods in Complexity Theory, Spring 2017.
5. [vMe] A course on Complexity Theory (offered by Dieter van Melkebeek) at University of Wisconsin-Madison: CS 880: Advanced Complexity Theory, Spring 2008.
6. [O'D1] A course on Boolean Function Analysis (offered by Ryan O'Donnell) at CMU: 15-859S 2007: Analysis of Boolean Functions, Spring 2007.
7. [O'D2] Ryan O'Donnell, "Analysis of Boolean Functions", Cambridge University Press, 2014. [DOI].
8. [O'D3] A course on Boolean Function Analysis (offered by Ryan O'Donnell) at CMU: 15-859S / 21-801A 2012: Analysis of Boolean Functions, Fall 2012.
9. [O'D3] Ryan O'Donnell, Hardness amplification within NP. J. Comput. Syst. Sci. 69(1): 68--94 (2004). [DOI]
10. [Tre] A course on graph partitioning and expansion (offered by Luca Trevisan) at Stanford: CS359G: Graph Partitioning and Expanders, Winter 2011.

#### Requirements

Students taking the course for credit will be expected to:

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

This page has been accessed at least times since Jul 1, 2017.