Sublinear-Time Algorithms for Max Cut, Max E2Lin(q), and Unique Label Cover on Expanders
share
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-ε from those with the optimal value less than 1-ρ for ρ≫ε. The time complexities for Max Cut and Max 2Lin(q) are O(1/ϕ^2ρ· m^1/2+O(ε/(ϕ^2ρ))) and O(poly(q/ϕρ)·(mq)^1/2+O(q^6ε/ϕ^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 ϕ≫ϵ in the bounded-degree model. The time complexity of our algorithm is O_d(2^q^O(1)·ϕ^1/q·ε^-1/2· n^1/2+q^O(q)·ε^4^1.5-q·ϕ^-2), where n is the number of variables. We complement these algorithmic results by showing that testing 3-colorability requires Ω(n) queries even on expanders.
READ FULL TEXT