Sublinear-Time Algorithms for Max Cut, Max E2Lin$(q)$, and Unique Label Cover on Expanders
Pan Peng, Yuichi Yoshida · arXiv (Cornell University) · 2022
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 $2$Lin$(q)$ are $\widetilde{O}(\frac{1}{ϕ^2ρ} \cdot m^{1/2+O(\varepsilon/(ϕ^2ρ))})$ and $\widetilde{O}(\mathrm{poly}(\frac{q}{ϕρ})\cdot {(mq)}^{1/2+O(q^6\varepsilon/ϕ^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 $\widetilde{O}_d(2^{q^{O(1)}\cdotϕ^{1/q}\cdot \varepsilon^{-1/2}}\cdot n^{1/2+q^{O(q)}\cdot \varepsilon^{4^{1.5-q}}\cdot ϕ^{-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.