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))
| 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] |
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.
Students taking the course for credit will be expected to:
This page has been accessed at least
times since Jul 1, 2017.
| Prahladh Harsha |
|