Abstract:
We consider the problem of testing bipartiteness in the adjacency matrix model. The best known algorithm, due to Alon and Krivelevich, distinguishes between bipartite graphs and graphs that are $\epsilon$-far from bipartite using $O((1/\epsilon^2)polylog(1/epsilon)$ queries. We show that this is optimal for non-adaptive algorithms, up to the polylogarithmic factor. We also show a lower bound of $\Omega(1/\epsilon^{3/2})$ for adaptive algorithms.