Analysis of Boolean Functions
CS 798-004: Advanced Research Topics, Fall 2017

CS 798-004: Analysis of Boolean Functions
Fall 2017

Term
Fall 2017

Lectures
Time: Thursdays, 4:00-6:50pm
Location: DC 2568

Instructor
Eric Blais
eric.blais@uwaterloo.ca

Teaching assistant
Amit Levi
amit.levi@uwaterloo.ca


What is this course about?

Many of the most fundamental questions in computer science are in fact questions about an elegant combinatorial object: the Boolean function. In this course, we will see how tools from Fourier analysis can be used to answer some of these questions, covering results in such varied areas as learning theory, sublinear-time algorithms, and circuit complexity.


What background do I need to take this class?

The most important requirement for the class is mathematical maturity, along with a solid understanding of combinatorics, probability theory, and the analysis of algorithms. No previous background in Fourier analysis will be required for the class.


What is the structure of the class?

The model of the class is a guided independent study of the topic. The weekly lectures will aim to be supplementary to the independent reading of the textbook by the students, with a focus on clarifying and expanding on the material from the book.

There will be 5 assignments containing selected exercises from the class textbook throughout the term. The students will also get to explore one of the topics covered in the course in more depth via a class project.


Where can I learn more about this course?

The textbook for the class is Analysis of Boolean Functions by Ryan O'Donnell. We will follow the textbook closely throughout the term, so the best way to see if the material is of interest to you is to read the first chapters of the book.


Assignments

The assignments will be added here as they become available.

Problem set 1.
Due on Sept 21. Solve the following problems from the textbook:
  • 1.3
  • 1.7
  • 1.21
  • 2.23
  • 2.56 parts (a) and (b)
Problem set 2.
Due on Oct 5.
Problem set 3.
Due on Oct 26.
Problem set 4.
Due on Nov 9.
Problem set 5.
Due on Nov 23.

Amit will also be regularly adding bonus problem sets below. Enjoy!

Bonus problem 1.
Influence and symmetry
Bonus problem 2.
The rise of Boolean functions

Project

More information on the class project will be added here.

List of topics

Fourier representation of Boolean functions
Boolean functions as vectors. Plancherel's Theorem and other basic facts.
Influence and noise stability
Boolean functions as social choice functions. Juntas. Discrete derivatives.
Learning via Fourier concentration
Decision trees. Low-Degree learning algorithm. Goldreich-Levin algorithm.
Small-depth circuits
DNF formulas. Random restrictions. Switching Lemma.
Threshold functions
Majority and linear threshold functions. Central Limit Theorem.
Pseudorandomness
Boolean functions as polynomials. Resilience. Bent functions.
Property testing
BLR test. Testing dictatorships. PCPPs
Hardness of approximation
CSPs. Hardness of 3SAT and 3LIN.
Hypercontractivity
Kahn-Kalai-Linial theorem. Friedgut's junta theorem.

Cover photo: Cubes ©Rob Hilken.
Site designed with Bootstrap.