The analysis of Boolean functions has been an important tool in many diverse areas of computer science, e.g., complexity theory, property testing, social choice theory and quantum computing. The aim of this course is to provide an introduction to the analysis of Boolean functions, different complexity measures on these Boolean functions and relationship between these complexity measures.
We will start with Fourier analysis on the Boolean hypercube, how it is defined and what are its important properties. These properties will be accompanied by applications in different areas of computer science. We will cover the concept of Fourier degree and approximate degree too. This back-ground material and applications will constitute around half of the course.
The remaining half will be composed of different complexity measures on Boolean functions and the relationship between them. We will cover mathematical complexity measures on Boolean functions like sensitivity, degree and certficate complexity. Other complexity measures coming from the computational world like decision tree complexity, randomized and quantum query complexity will also be discussed. The course will also deal with relations known between these complexity measures from different domains. Most of these were polynomially related and we will give proof of these relationships. If time permits, we will cover the recent breakthrough result of Huang which shows that even sensitivity is polynomially related to other complexity measures.
Boolean Functions
Linear Algebra