Jeff Xu: Average-Case Sum-of-Squares Lower Bounds for Cryptographers

Abstract: The Sum-of-Squares (SoS) hierarchy of semidefinite programs is a powerful algorithmic paradigm which captures state-of-the-art algorithmic guarantee, and in the average case setting, SoS lower bounds provide strong evidence of algorithmic hardness or information-computation gaps. I will discuss the techniques for proving lower Bounds for statistical problems, and if time permitted, sketch upon some major challenges addressed in recent works. Despite the progress in this field, it has not attracted much attention from the crypto community. Towards this end, I will try to mention few challenges residing in the intersection of these two areas.