Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR02-064 | 14th November 2002 00:00

#### Lower Bounds for Testing Bipartiteness in Dense Graphs

TR02-064
Authors: Andrej Bogdanov, Luca Trevisan
Publication: 3rd December 2002 12:30
Keywords:

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.

ISSN 1433-8092 | Imprint