Coloring 3-Colorable Graphs with Low Threshold Rank

We present a new algorithm for finding large independent sets in 3-colorable graphs with small 1-sided threshold rank. Specifically, given an \(n\)-vertex 3-colorable graph whose uniform random walk matrix has at most \(r\) eigenvalues larger than \(\varepsilon\), our algorithm finds a proper 3-coloring on at least \((\frac12 - O(\varepsilon))n\) vertices in time \(n^{O(r/\varepsilon^2)}\). This extends and improves upon the result of Bafna, Hsieh, and Kothari [6] on 1-sided expanders. Furthermore, an independent work by Buhai, Hua, Steurer, and Vari-Kakas [13] shows that it is UG-hard to properly 3-color more than \((\frac12 + \varepsilon)n\) vertices, thus establishing the tightness of our result.