Simone Maria Giancola (LMO)
Low-degree lower bounds via almost orthonormality
In this lecture, I will introduce the concept of lower bounds on classes of algorithms as opposed to information theoretic lower bounds. While these results are based on conjectures, I will argue that in nice cases they are useful and meaningful.
After this quick introduction, we will see a shortcoming of the classical technique to prove these results, and a principled way to fix it based on recent work.
