Lower bounds for testing bipartiteness in dense graphs

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 ε-far from bipartite using 0(1/ε²) queries. We show that this is optimal for non-adaptive algorithms, up to polylogarithmic factors. We also show a lower bound of Ω(1/ε³2/) for adaptive algorithms.