## CS 698Q: Complexity Measures for Boolean Functions

### Announcements

• The link for projects is here . Please submit an introductory report by Oct. 8th (around 1.5 pages, introducing the paper).
• The link for class notes (to be prepared) is here .
• The online endsem is scheduled on 25/11/21 (Thursday) from 4-7 PM.

### 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

### 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, sign 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

• Analysis of Boolean functions, Ryan O'Donnell.
• Complexity Measures and Decision Tree Complexity: A Survey, Harry Buhrman and Ronald de Wolf.
• A Brief Introduction to Fourier Analysis on the Boolean Cube, Ronald de Wolf.

### Linear Algebra

• Linear Algebra and its Applications, G. Strang.
• Matrix Analysis, Bhatia.