Lifting Sum-of-Squares Lower Bounds: Degree-$2$ to Degree-$4$

Sidhanth Mohanty, Prasad Raghavendra, Jeff Xu

The degree-$4$ Sum-of-Squares (SoS) SDP relaxation is a powerful algorithm that captures the best known polynomial time algorithms for a broad range of problems including MaxCut, S…