Courses

236646 Boolean Function Analysis Spring 2019

During the 2019 spring semester I gave a self-study course on Boolean Function Analysis.

Subjects covered:

  • Basics:
    • Fourier expansion.
    • Orthogonality.
    • Linearity testing.
    • Influence.
    • Fourier levels.
    • Nisan–Szegedy (optional).
    • Noise operator.
  • Hypercontractivity:
    • 4-to-2 hypercontractivity.
    • Friedgut–Kalai–Naor theorem.
    • Kahn–Kalai–Linial theorem.
    • Friedgut’s junta theorem.
    • $p$-to-$q$ hypercontractivity.
  • Biased hypercube:
    • $p$-biased Fourier analysis.
    • Erdős–Ko–Rado theorem.
    • Friedgut–Kalai sharp threshold theorem.
  • Invariance principle:
    • Gaussian space.
    • Invariance principle.
    • Majority is stablest.

Only few got to the biased hypercube, and nobody made it to the invariance principle.

Exercise sheets are available in two versions: plain, and with hints.

OTHER SEMESTERS

  • 236646 Boolean Function Analysis Winter 2015/2016 website