Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR02-064 | 14th November 2002 00:00

Lower Bounds for Testing Bipartiteness in Dense Graphs

RSS-Feed




TR02-064
Authors: Andrej Bogdanov, Luca Trevisan
Publication: 3rd December 2002 12:30
Downloads: 3214
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