Lower Bounds for Testing Bipartiteness in Dense Graphs

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Andrej Bogdanov Articles by Luca Trevisan

19th Annual IEEE Conference on Computational Complexity (CCC'04)

Amherst, Massachusetts

June 21-June 24

ISBN: 0-7695-2120-7

	ASCII Text	x
	Andrej Bogdanov, Luca Trevisan, "Lower Bounds for Testing Bipartiteness in Dense Graphs," Computational Complexity, Annual IEEE Conference on, pp. 75-81, 19th Annual IEEE Conference on Computational Complexity (CCC'04), 2004.

	BibTex	x
	@article{ 10.1109/CCC.2004.1313803, author = {Andrej Bogdanov and Luca Trevisan}, title = {Lower Bounds for Testing Bipartiteness in Dense Graphs}, journal ={Computational Complexity, Annual IEEE Conference on}, volume = {0}, year = {2004}, issn = {1093-0159}, pages = {75-81}, doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2004.1313803}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Computational Complexity, Annual IEEE Conference on TI - Lower Bounds for Testing Bipartiteness in Dense Graphs SN - 1093-0159 SP75 EP81 A1 - Andrej Bogdanov, A1 - Luca Trevisan, PY - 2004 KW - null VL - 0 JA - Computational Complexity, Annual IEEE Conference on ER -

Andrej Bogdanov, University of California at Berkeley

Luca Trevisan, University of California at Berkeley

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2004.1313803

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 \mathop 0\limits^ \sim (1/\varepsilon ^2 ) queries. We show that this is optimal for non-adaptive algorithms, up to polylogarithmic factors. We also show a lower bound of \Omega (1/\varepsilon ^{3/2} ) for adaptive algorithms.

Citation:

Andrej Bogdanov, Luca Trevisan, "Lower Bounds for Testing Bipartiteness in Dense Graphs," ccc, pp.75-81, 19th Annual IEEE Conference on Computational Complexity (CCC'04), 2004

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.