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)
Here are the solutions for this assignment, courtesy of Amit Levi.

Problem set 2.
Due on Oct 5. Solve the following problems from the textbook:
  • 3.15
  • 3.16
  • 3.35
  • 4.12
You may use this template, courtesy of Nolan Shaw, for your solution.

Problem set 3.
Due on Oct 26. Solve the following problems from the textbook:
  • 5.4
  • 5.6
  • 5.13
  • Bonus: 5.14
Solution template, again courtesy of Nolan Shaw.

Problem set 4.
Due on Nov 9. Solve two of the following problems from the textbook:
  • 7.18
  • 7.29
  • 7.30
These problems guide you through the proofs of Theorems 7.19, 7.40, and 7.41, respectively. You are encouraged to try to prove the theorems directly before doing the problems. Here is a solution template, again courtesy of Nolan Shaw.

Problem set 5.
Due on Nov 23. Solve three of the following problems from the textbook:
  • 9.2
  • 9.6
  • 9.20
  • 8.23
  • Bonus: 8.47 + (extra bonus!) the related Aaronson-Ambainis conjecture discussed in the notes.

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

The purpose of the course project is to enable a more in-depth study of a question related to the analysis of Boolean functions.

This project can take many different forms, but the most straightforward way to approach it is to identify a state-of-the-art result that you find particularly interesting and then work on understanding it very well: its context (i.e., why the result is interesting; what was known before it), its proof, and what is an interesting open problem that is suggested but not covered by the result. You should then try to solve that open problem and describe what you tried (and what partial—or complete!—results you obtained), but new results are not required for the final project to be successful.

There are three deliverables for the project:

  1. A project proposal (handed in and discussed on Oct 19)
  2. A short presentation (on Nov 30)
  3. A final project report (due on Dec 14)

The presentation will be a short 10 minute overview of your project. The goal of your presentation is to describe the topic of your project to the rest of the class and, most importantly, why it might be interesting for them. Given the short time we have for the talks, you are encouraged to make (a very small number of) slides for your talk, though you are free to use the board instead if you prefer to do so.

The final project report should be typeset in LaTeX and presented in the format of a research article. I.e., with an introduction that describes the topic you studied and presents the context (high-level motivation, related results, etc.) for this topic, followed by more technical sections where (i) you provide a complete proof of the main result you studied (in your own words), and (ii) describe the approaches and partial results obtained on the open problem you tackled. There is no upper or lower limit on the length of the final project report, around 10 pages (say, 6-14 pages) should be both necessary and sufficient for almost everyone.

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.