School — PAC (probably approximately correct) learning and Boolean Harmonic Analysis

The interaction between learning theory and harmonic analysis was emphasized by mathematics of quantum computing. One of the outstanding open problems in this area concerns the sharp estimates in Bohnenblust-Hille inequality that generalizes a celebrated Littlewood’s lemma. How to learn (with small error and with large probability) a complicated function or a very large matrix in a relatively small number of random (quantum) queries? Of course, there should be some Fourier type restrictions on a function (a matrix) to have a reasonable answer to this. The “classical” way of learning (Boolean) functions comes from very sophisticated extensions of theorems of Kahn—Kalai—Linial type. In those results the interplay between maximal influence and heavy Fourier tails is the main technique. Maximal influence should be large if the `tail’ is small. However, recently another approach that is hinged on Bohnenblust—Hille inequality appeared. The school will cover the classical maximal influence approach to `probably approximately correct' (PAC) learning as well as the recent achievements using Bohnenblust—Hille inequality and its quantum counterpart.