On Testing Bipartiteness in the Bounded-Degree Graph Model

A complexity improvement for the rapidly mixing case, which can be used as a project.

Webpage by Oded Goldreich

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 {\em the book}). The purpose of this variation is to show that, {\em when the graph is rapid mixing, Bipartiteness can be tested in $O({\sqrt k})$ time, rather than in ${\widetilde O}({\sqrt k})$ time.}

Much of the 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\ell$-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 $\ell^2\cdot(m^2-m)$ collision events (rather than the $\cdot(m^2-m)$ events considered in the book).

The project may be defined as proving Lemma 3. The statements of Claims 3.1 and 3.2 can serve as hints, but the project may still be too hard even with these hints. Specifically, the students should be able to prove Claim 3.1, but proving of Claim 3.2 may require an additional hint (e.g., the random variables to be used in the proof).

Material available on-line

Back to either Oded Goldreich's homepage or general list of papers.