Faster MAX-CUT on Bounded Threshold Rank Graphs

Prashanti Anderson, Samuel B. Hopkins, Amit Rajaraman +1

We design new algorithms for approximating 2CSPs on graphs with bounded threshold rank, that is, whose normalized adjacency matrix has few eigenvalues larger than $\epsilon$, sm…