## Comp 760 Analysis of Boolean Functions

 Instructor Hamed Hatami Lectures Tuesday-Thursday 4:05-5:25pm at ENGMC 103.

## Description

This course is intended for graduate students in theoretical computer science or mathematics. Its purpose is to study Boolean functions via tools from various areas of mathematical analysis (e.g. Fourier analysis, functional analysis, convex geometry). This analytic approach plays an essential role in modern theoretical computer science, and it is the key to understanding many fundamental concepts such as pseudo-randomness. In this course there will be an emphasis on the applications to the following areas:

• Machine learning,
• Circuit complexity,
• Communication complexity,
• Hardness of approximation,
• Study of Social choice.

The main prerequisite is mathematical maturity and familiarity with basic background in linear algebra, mathematics analysis, and probability theory.

## Grading

There is no exam in this course. The final grade will be based on assignments and a final presentation.

### Resources

• Analysis of Boolean Functions, by Ryan O'Donnell.
• Lecture notes from a similar course I offered in 2014.

## Projects:

### Lectures

• Boolean Functions and the Fourier Expansion. Reading: Sections 1.1, 1.2, 1.3, 1.4 of Ryan's book, and Chapter 2 of my lecture notes. Exercises 1.

• BLR test. Reading: Sections 1.5, 1.6 of Ryan's book.

• Social Choice. Reading: Sections 2.1, 2.2, 2.3 of Ryan's book.

• Social Choice. Reading: Sections 2.4, 2.5 of Ryan's book.

• PAC learning. Reading: Sections 3.4 of Ryan's book.

• Fourier spectrum and circuit complexity. Reading: Chapter 4 from Lecture notes.

• Degree, approximate degree, decision tree, block sensitivity and sensitivity. Reading: Buhrman and de Wolf's survey Complexity Measures and Decision Tree Complexity.

• Hyper-contractivity and KKL inequality. Reading: Chapter 6 from Lecture notes.

• Sander's quasi-polynomial bound on polynomial Freiman-Ruzsa conjecture Here.