About the Courses

Boaz Barak: Sums of Squares

I am going to give a tutorial on the "Sum of Squares" (also known as "Lasserre") semidefinite programming hierarchy from a theoretical computer science perspective. This is a natural algorithm for solving polynomial equations that has been proposed by researchers from different communities, and has recently been the object of much interest in TCS because it is a natural candidate algorithm to tackle some longstanding open questions.

I will give an introduction to this algorithm and its connection to classical questions in mathematics on certifying that a function is non-negative by writing it as a sum of squares. I will then present some of the applications of this algorithm, as well as known lower bounds, and how both can be analyzed using the above connection. There is much we don't know about this algorithm, and so I will also discuss some of the many open problems and research directions in this area. The course will be accessible to beginning graduate students in TCS and will not assume prior knowledge in convex optimization or algebraic geometry (at least I hope so, because I don't have any...).

Ryan O'Donnell: Analysis of Boolean Functions

Boolean functions, f : {0,1}^n -> {0,1}, are perhaps the most basic object of study in computer science. In this workshop we will investigate them via their Fourier transform and other analytic methods. Besides developing basic techniques, we will see the emergence of a number of themes:

• The dichotomy between juntas and functions with small influences.
• Noise stability as a bridge between combinatorial and Fourier-analytic properties of a function.
• The Boolean cube is a small-set expander.
• Functions on Gaussian space are a special case of Boolean functions.
• Low-degree functions of well-behaved random variables are well-behaved.
• Invariance: for low-influence functions, only the first two moments of the inputs matter.

Finally, we will see the tools and themes of Analysis of Boolean Functions applied to problems in learning theory, communication complexity, property testing, NP-hardness of approximation, and random graph theory.