Taibleson Colloquium: Quantum and classical low degree PAC learning, Harmonic analysis, and dimension-free Remez inequality

Abstract: The talk is based on recent works with Lars Becker, Ohad Klein, Joseph Slote, and Haonan Zhang. Recent efforts in Analysis of Boolean Functions aim to extend core results to new spaces, including noncommutative spaces (matrix algebras).

Suppose you wish to find a 2^n by 2^n matrix by asking this matrix question that it honestly answers. For example you can ask questions "What is your (i,j) element?" Obviously you will need exponentially many questions. But if one knows some information on Fourier side one can ask only log n questions if they are carefully randomly chosen. One pays the price:  one would find the matrix only with high confidence, and with a small error. Such learning is known as PAC; PAC stands for 'probably approximately correct'. 
The origins of the problem are in theoretical computer science, but the methods are pure harmonic analysis and probability. I will explain how this can be done using harmonic analysis and probability. The main ingredient is dimension free Bernstein-Remez inequality.

This inequality is the key ingredient that allows us to extend to new spaces a recent series of algorithms for learning low-degree polynomials on the hypercube and low-degree quantum observables on qubits.

Host: Alan Chang

Pre-Talk Reception at Cupples I, Room 200 (Lounge) from 3:00pm to 4:00pm