3-0-0-0 (9)
Linear algebra.
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 the relationship between these complexity measures.
We will start with a 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, sign degree and approximate degree too. This background material and applications will constitute around half of the course.
The next half will start with combinatorial complexity measures on Boolean functions like sensitivity, block sensitivity and certificate complexity. We will then talk about complexity measures coming from the computational world like decision tree complexity, randomized decision tree and quantum query complexity.
The final part of the course will 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.