Abstract: Sum-of-Squares lower bounds are arguably the strongest evidence we have for algorithmic intractability in the average-case setting. Despite the steady flow of progress in the dense regime, our understanding remains rather limited in the sparse regime, even for just degree-4 SoS.
Among various obstacles, a major difficulty is to understand the spectral behaviors of a large class of random matrices with correlated entries. In fact, non-trivial challenges posed by sparsity are already present in the adjacency matrix of random graphs with a bounded average degree.
In this talk, I will describe how we overcome this technical challenge by proposing a "local" reinterpretation of trace-method. As a result, the substantially refined understanding allows us to
1) in the ultra-sparse regime, obtain the first higher-degree Sum-of-Squares lower bounds in $G_{n,d/n}$ for $d=O(1)$ for independent set and coloring;
2) in the dense-regime, obtain a sharper bound for the ellipsoid fitting conjecture that is tight up-to an absolute constant;
3) in the intermediate regime, obtain tight hardness for the Densest-$k$-Subgraph problem matching log-density framework.