Abstract: Recently the TCS query learning ala Nisan--Mansur--Linial got the boost from a harmonic analysis random algorithm. This problem has a non-commutative version where one needs to learn a very big matrix (so-called d-local hamiltonians) from a few random queries.
The corresponding harmonic analysis results have a drawback that it is still not known how tight they are. We will discuss this and show tightness for some of them. Interestingly, one such tightness result is closely related to Einstein--Podolsky--Rosen paradox from quantum mechanics. On a close issue: arguably the main problem in understanding the speed up of quantum algorithms versus classical ones for a certain collection of problems (called Aaronson--Ambainis conjecture and still open) will be discussed too if time permits.