{"ID":2841841,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.11499","arxiv_id":"2511.11499","title":"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 $\\varepsilon$, smaller than $-\\varepsilon$, or both. Unlike on worst-case graphs, 2CSPs on bounded threshold rank graphs can be $(1+O(\\varepsilon))$-approximated efficiently. Prior approximation algorithms for this problem run in time exponential in the threshold rank and $1/\\varepsilon$. Our algorithm has running time which is polynomial in $1/\\varepsilon$ 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(\\varepsilon))$ approximation for MAX-CUT on bounded threshold rank graphs running in $\\mathrm{poly}(1/\\varepsilon)$ 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.","short_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 $\\varepsilon$, smaller than $-\\varepsilon$, or both. Unlike on worst-case graphs, 2CSPs on bounded threshold rank graphs can be $(1+O(\\varepsilon))$-approxim...","url_abs":"https://arxiv.org/abs/2511.11499","url_pdf":"https://arxiv.org/pdf/2511.11499v1","authors":"[\"Prashanti Anderson\",\"Samuel B. Hopkins\",\"Amit Rajaraman\",\"David Steurer\"]","published":"2025-11-14T17:20:20Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}