Event Type
Harmonic analysis on boolean cube and beyond and some application to learning
Thursday, January 18, 2024 4:30 PM
Alexander Volberg (Michigan State University)

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 question ``What is your (1,1) element?’’

Obviously you will need exponentially many questions like that. But if one knows some information on Fourier side then one can ask only log n questions if they are carefully randomly chosen.

Of course one pays the price: first of all one would find the matrix only with high confidence (high probability bigger than 1-\delta), secondly with  the error \epsilon.

I will explain how this can be done using harmonic analysis and probability. The main ingredient is dimension free Remez inequality.


You can learn more about Professor Sasha Volberg here: https://users.math.msu.edu/users/volberg/