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

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

- (1 lecture) Hardness amplification
- (3 lectures) Spectral structure and concentration, Goldreich-Levin theorem, DNF formulae and AC0 circuits, Linial-Mansour-Nisan
- (4 lectures) Majority and threshold functions, Fourier
coefficients of Majority, Level-1 theorem, 2/\pi- theorem, Peres'
theorem, Central Limit theorem, Berry-Esseen theorem

**27 Sep: pset 1 due, pset 2 out** - (3 lectures) Hardness of approximation, Hastad's 3-bit dictator
tests, PCPs, PCPs of proximity, Unique Games

**16 Oct: pset 2 due, pset 3 out** - (1 lecture) General Domains, p-biased Fourier, Erdos-Ko-Rado theorem, Randomized decision tree complexity
- (4 lectures) Hypercontractivity, Bonami's Lemma,
Kahn-Kalai-Linial theorem, Friedgut-Kalai-Naor theorem,
Kindler-Safra theorem

**1 Nov: pset 3 due, pset 4 out** - (3 lectures) Advanced hypercontactivity, sharp threshold
theorems

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

**6 Dec: pset 5 due, pset 6 (???) 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.

**[Har]**A course on PCPs (offered by Prahladh Harsha) at TIFR and IMSc: Limits of approximation algorithsm: PCPs and Unique Games.**[O'D1]**A course on Boolean Function Analysis (offered by Ryan O'Donnell) at CMU: 15-859S 2007: Analysis of Boolean Functions.**[O'D2]**Ryan O'Donnell, "Analysis of Boolean Functions", Cambridge University Press, 2014. [DOI].

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 |