Sublinear-Time Algorithms for Max Cut, Max E2Lin(q), and Unique Label Cover on Expanders

We show sublinear-time algorithms for Max Cut and Max E2Lin(q) on expanders in the adjacency list model that distinguishes instances with the optimal value more than 1-varepsilon from those with the optimal value less than 1-ρ for ρ gg varepsilon. The time complexities for Max Cut and Max 2Lin(q) are widetildeO(frac1φ2ρ · m1/2+O(varepsilon/(φ2ρ))) and widetildeO(poly(fracqφρ)· (mq)1/2+O(q6varepsilon/φ2ρ2)), respectively, where m is the number of edges in the underlying graph and φ is its conductance. Then, we show a sublinear-time algorithm for Unique Label Cover on expanders with φ gg ε in the bounded-degree model. The time complexity of our algorithm is widetildeOd(2^qO(1)·φ1/q· varepsilon-1/2· n^1/2+qO(q)· varepsilon^41.5-q· φ-2), where n is the number of variables. We complement these algorithmic results by showing that testing 3-colorability requires Omega(n) queries even on expanders.