  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-\rho$
for $\rho \gg \varepsilon$. The time complexities for Max Cut and Max
$2$Lin$(q)$ are $\widetilde{O}(\frac{1}{\phi^2\rho} \cdot
m^{1/2+O(\varepsilon/(\phi^2\rho))})$ and
$\widetilde{O}(\mathrm{poly}(\frac{q}{\phi\rho})\cdot
{(mq)}^{1/2+O(q^6\varepsilon/\phi^2\rho^2)})$, respectively, where $m$ is the
number of edges in the underlying graph and $\phi$ is its conductance. Then, we
show a sublinear-time algorithm for Unique Label Cover on expanders with $\phi
\gg \epsilon$ in the bounded-degree model. The time complexity of our algorithm
is $\widetilde{O}_d(2^{q^{O(1)}\cdot\phi^{1/q}\cdot \varepsilon^{-1/2}}\cdot
n^{1/2+q^{O(q)}\cdot \varepsilon^{4^{1.5-q}}\cdot \phi^{-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.

Data Structures and Algorithms