Comp 760

Analysis of Boolean Functions

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.

Assignments and exercises

• Exercises 1.
• Exercises 2.
• Homework 1 Due Feb 7th.
• Homework 2 Due March 7th.

Projects:

• J. Hastad, An average-case depth hierarchy theorem for higher depths. (Two students)
• Hamed Hatami, Kaave Hosseini, Shachar Lovett. Structure of protocols for XOR functions. (Yaqiao)
• Ehud Friedgut, Oded Regev, Kneser graphs are like Swiss cheese. (Ying Jie)
• Anindya De, Michael Saks, Sijian Tang, Noisy population recovery in polynomial time. (Lianna)
• Daniel Kane, The Average Sensitivity of an Intersection of Half Spaces.
• Mark Braverman, Poly-logarithmic independence fools AC0 circuits.

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.