View article

This memo presents a variant of the known tester of Bipartiteness in the bounded-degree graph model, which is presented in Section 9.4. 1 of my book on Property Testing (hereafter referred to as the book). The purpose of this variation is to show that, when the graph is rapid mixing, Bipartiteness can be tested in O (√ k) time, rather than in O (√ k) time.

Much of the following text is reproduced from Section 9.4. 1 of the book, and the essence of the improvement is in capitalizing on half of the vertices that appear on each (2ℓ-step long) random walk rather than using only the last vertex in each of the m walks. This is reflected in the proof of Claim 3.2, where we consider ℓ2·(m2− m) collision events (rather than the·(m2− m) events considered in the book).