Boolean Function Complexity

Boolean functions are perhaps the most basic objects of study in the domain of theoretical computer science. In this course we will discuss analysis of Boolean functions and various applications in several areas like property testing, circuit complexity, learning theory, pseudorandomness.

- Boolean functions, computational models [Lecture Note]
- Fourier expansion- Boolean functions as polynomial [Lecture Note]
- BLR test, influence and sensitivity [Lecture Note]
- Average sensitivity bound for constant depth circuits [Lecture Note]
- Proof of Hastad’s Switching Lemma [Lecture Note]
- Monotone circuit lower bound of CLIQUE [Lecture Note]
- More on monotone circuit lower bounds [Lecture Note]
- Introduction to learning theory [Lecture Note]
- Goldreich-Levin algorithm, Tribes, KKL theorem [Lecture Note]
- Completing the proof of KKL theorem [Lecture Note]
- Introduction to pseudorandomness [Lecture Note]
- Fooling F
_{2}-polynomials [Lecture Note]

Boolean Function Complexity: Advances and Frontiers

by Stasys JuknaAnalysis of Boolean Functions

by Ryan O’Donnell

- Assignment 1; due on 28.11.16
- Assignment 2; due on 10.01.17

For any clarification regarding the course, feel free to meet me anytime at Room #324 or drop me an e-mail at <firstname> at iuuk dot mff dot cuni dot cz.