Trimester Program Activity — School “PAC (probably approximately correct) learning and Boolean Harmonic Analysis”

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.