Sum-of-Squares Lower Bounds for Densest $k$-Subgraph

Chris Jones, Aaron Potechin, Goutham Rajendran +1

Given a graph and an integer $k$, Densest $k$-Subgraph is the algorithmic task of finding the subgraph on $k$ vertices with the maximum number of edges. This is a fundamental probl…