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 Set 1 [pdf (out: 11 Sep, due: 27 Sep)]
- Problem Set 2 [pdf (out: 27 Sep, due: 16 Oct)]
- Problem Set 3 [pdf (out: 6 Nov, due: 20 Nov)]

4 Sep |
1. IntroductionAdministrivia, Introduction to Analysis of Boolean Functions, Overview of course Ref: [O'D1 (Lecture 1)] |

6 Sep |
2. Fourier Expansion and Linearity testingRef: [Har (Lecture 6, Sec 6.1), O'D2 (Chap 1)] |

11 Sep |
3. Hastad's 3-bit PCPs - Part IDictator 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 IILong code, dictators, Hastad's MAX3LIN2 test Ref: [Har (Lecture 11, Sec 11.3 and 11.5)] |

18 Sep |
5. Voting theory and Social ChoiceInfluence, noise stability, Condorcet's paradox, Arrow's theorem Ref: [O'D2 (Chap 2)] |

20 Sep |
6. Voting theory and spectral concentrationKalai'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 learningSpectral 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 theoremKushilevitz-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 DNFsLearning 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 functionsLMN 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 lemmaImpagliazzo'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 NPHardness 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 PTFsNoise 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 MajorityPeres' 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 HypercontractivityFourier coefficients of Majority, Hypercontractivity, Bonami's lemma Ref: [O'D2 (Sec 5.3 and 9.1)] |

30 Oct |
16. Hypercontractivity and FKN TheoremSmall 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 hypercubesmall 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 TheoremWeight-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 hypercubeFriedgut'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 TheoremRusso-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
CoverIntroduction to Unique Games, UG-hardness of approximating vertex cover Ref: [notes] |

20 Nov |
22. The Hypercontractivity theorem for hypercubeApplications 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)] |

- (3 lectures) Advanced hypercontactivity, Berry Esseen theorem,
majority is stablest, sharp threshold
theorems

- (3 lectures) Hardness of approximation, Hastad's 3-bit dictator
tests, PCPs, PCPs of proximity, Unique Games

**20 Nov: pset 3 due, pset 4 out** - (3 lectures) Other topics

**6 Dec: pset 4 due, pset 5 (???) out**

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.

**[Fil]**A course on Boolean Function Analysis (offered by Yuval Filmus) at Technion: Analysis of Boolean Functions, Winter 2015-16.**[Har]**A course on PCPs (offered by Prahladh Harsha) at TIFR and IMSc: Limits of approximation algorithsm: PCPs and Unique Games.**[HVV]**Alexander Healy, Salil P. Vadhan, Emanuele Viola: Using Nondeterminism to Amplify Hardness. SIAM J. Comput. 35(4): 903-931 (2006). [DOI]**[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.**[vMe]**A course on Complexity Theory (offered by Dieter van Melkebeek) at University of Wisconsin-Madison: CS 880: Advanced Complexity Theory, Spring 2008.**[O'D1]**A course on Boolean Function Analysis (offered by Ryan O'Donnell) at CMU: 15-859S 2007: Analysis of Boolean Functions, Spring 2007.**[O'D2]**Ryan O'Donnell, "Analysis of Boolean Functions", Cambridge University Press, 2014. [DOI].**[O'D3]**Ryan O'Donnell, Hardness amplification within NP. J. Comput. Syst. Sci. 69(1): 68--94 (2004). [DOI]-
**[Tre]**A course on graph partitioning and expansion (offered by Luca Trevisan) at Stanford: CS359G: Graph Partitioning and Expanders, Winter 2011.

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.

Prahladh Harsha |