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

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

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

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!