PhD course on Analysis of Boolean Functions and some applications in theoretical computer science
Tid: Må 2018-02-05 kl 10.00
Plats: Room 4523, Floor 5, Lindstedtsvägen 5, KTH
Medverkande: Per Austrin and Johan Håstad
Brief outline of course contents:
- The Fourier transform of a Boolean function and its properties.
- Norm inequalities, hypercontractivity, and isoperimetric inequalities on the Boolean cube.
- Analysis of functions on Gaussian space and invariance principles.
- Applications in theoretical computer science: circuit complexity, learning, hardness of approximation.
Required background: linear algebra and probability theory.
The first meeting is Monday Feb 5, 10-12, in room 4523 (5th floor of Lindstedtsvägen 5).