Speakers and topics

Ronald de Wolf

My lecture course was on Fourier analysis of Boolean functions.

Fourier analysis of functions on the Boolean cube has become one of the strongest and most versatile tools in theoretical computer science and discrete mathematics in the last few decades. The key idea is to view the set of 2ⁿ parity-functions as an orthonormal basis for the space of all functions f:{0,1}ⁿ→R, and to decompose a given f (say, the characteristic function of some subset of {0,1}ⁿ, or a probability distribution) in that basis. The coefficients in that linear decomposition are the Fourier coefficients of f, and the properties of f can often be fruitfully studied by considering its Fourier coefficients.

This mini-course provided an introduction to this toolbox and its applications. The five days of the course covered the following:

1. Introduction: basic definitions and examples.
2. More advanced topics, hypercontractive inequality.
3. Applications to mathematics: isoperimetry, approximating polynomials.
4. Applications to computer science: linearity testing, learning.
5. Applications to social choice: influence of voters on outcomes, Arrow's theorem.

Further reading: For a first introduction see my survey paper from Theory of Computing. For a much more comprehensive treatment see Ryan O'Donnell's book "Analysis of Boolean functions", Cambridge University Press, 2014.

Samuel Fiorini

Which combinatorial optimization problems can be modeled by a linear or semidefinite program, when the number of constraints and variables are limited? This fundamental question is arguably the main question addressed by the emerging field of extended formulations. This field has connections to many others, including convex geometry, communication complexity, circuit complexity and hardness of approximation.

My lectures provided an introduction to the field, illustrate some of these connections, and feature some recent results. The tentative schedule for the five days is as follows:

1. LP extended formulations: examples and construction methods.
2. Examples and constructions (continued). Yannakakis's factorization theorem, extended formulations from communication protocols.
3. Size lower bounds for (exact) extended formulations.
4. The Sherali-Adams (SA) hierarchy: definition and properties; Sherali-Adams integrality gap construction for Max-Cut.
5. Optimality of Sherali-Adams for CSPs.

Schedule

8:40-9:00, coffee
9:00-10:30, Lecture 1
10:30-10:50, coffeee break
10:50-12:20, Lecture 2
14:00-16:00 exercise classes

The event was held in the premises of the Institute of Mathematics of the Czech Academy of Sciences, Zitna 609/25, 110 00 Praha 1.