CS 672: Complexity Measures for Boolean Functions

Announcements

Course Notes

Topic Link
Introduction to Boolean functions Introduction
Polynomial representation and properties Fourier analysis
Influence, stability and social choice theory Influence
Decision tree complexity, randomized and quantum query complexity Decision tree
Approximate degree, lower bounds on quantum query Approximate degree
Lower bound on randomized query complexity, Yao's minimax Lower bounds
Sensitivity and other complexity measures Sensitivity
Proof of Sensitivity Conjecture: Huang Huang's result
Communication complexity and lower bounds Communication

Administrative details:

Course description:

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.

References

Boolean Functions

Linear Algebra