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

Chris Jones, Aaron Potechin, Goutham Rajendran, Jeff Xu

Browse the full STOC paper archive.