Faster MAX-CUT on Bounded Threshold Rank Graphs

Abstract

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$, smaller than $-\epsilon$, or both. Unlike on worst-case graphs, 2CSPs on bounded threshold rank graphs can be $(1+O(\epsilon ))$-approximated efficiently. Prior approximation algorithms for this problem run in time exponential in the threshold rank and $1/\epsilon$. Our algorithm has running time which is polynomial in $1/\epsilon$ and exponential in the threshold rank of the label-extended graph, and near-linear in the input size. As a consequence, we obtain the first $(1+O(\epsilon ))$ approximation for MAX-CUT on bounded threshold rank graphs running in $\mathrm{poly}(1/\epsilon )$ time. We also improve the state-of-the-art running time for 2CSPs on bounded threshold-rank graphs from polynomial in input size to near-linear via a new comparison inequality between the threshold rank of the label-extended graph and base graph. Our algorithm is a simple yet novel combination of subspace enumeration and semidefinite programming.

20 pages