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

Abstract

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-\epsilon$ from those with the optimal value less than $1-\ddot{I}$ for $\ddot{I}\gg \epsilon$. The time complexities for Max Cut and Max $2$Lin$(q)$ are $\tilde{O}(\frac{1}{\ddot{I}{•}^2\ddot{I}}\cdot m^{1/2+O(\epsilon /(\ddot{I}{•}^2\ddot{I}))})$ and $\tilde{O}(\mathrm{poly}(\frac{q}{\ddot{I}•\ddot{I}})\cdot {(mq)}^{1/2+O(q^6\epsilon /\ddot{I}{•}^2\ddot{I}{}^2)})$, respectively, where $m$ is the number of edges in the underlying graph and $\ddot{I}•$ is its conductance. Then, we show a sublinear-time algorithm for Unique Label Cover on expanders with $\ddot{I}•\gg \hat{I}\mu$ in the bounded-degree model. The time complexity of our algorithm is ${\tilde{O}}_d(2^{q^{O(1)}\cdot \ddot{I}{•}^{1/q}\cdot {\epsilon }^{-1/2}}\cdot n^{1/2+q^{O(q)}\cdot {\epsilon }^{4^{1.5-q}}\cdot \ddot{I}{•}^{-2}})$, where $n$ is the number of variables. We complement these algorithmic results by showing that testing $3$-colorability requires $\hat{I}\text{c◯}(n)$ queries even on expanders.

To appear in SODA'23