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


Time: Mon 11:30-13:00, Wed 14:00-15:30
Location: A201
Instructors :
Homepage: http://www.tcs.tifr.res.in/~prahladh/teaching/2017-18/fourier/

Course Calendar (Click here to subcribe to the calendar (ical format))


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)]

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)]

Tentative schedule for Future Lectures


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] Ryan O'Donnell, Hardness amplification within NP. J. Comput. Syst. Sci. 69(1): 68--94 (2004). [DOI]
  9. [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:

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


Prahladh Harsha
Valid HTML 4.01! Valid CSS!