loading...
Lower Bounds for Testing Bipartiteness in Dense Graphs
Amherst, Massachusetts June 21-June 24
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2004.131380319th Annual IEEE Conference on Comput ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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
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
Usage of this product signifies your acceptance of the Terms of Use.