How to learn N by N matrix by asking log log N question by using dimension free Remez inequality

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/