next up previous
Next: The Random Oracle Methodology, Up: Sabbatical at MIT (1996-1998) Previous: On the Limits of

A Sublinear Bipartitness Tester for Bounded Degree Graphs

This work presents an almost optimal tester for bipartiteness in the bounded-length incidence lists model. The tester works by uniformly selecting a few start vertices, and taking many random walks on the graph from each start vertex, where the number of walks is approximately the square root of the number of vertices in the graph, and each walk has poly-logarithmic length. The tester accepts if and only if the subgraph seen by these walks is bipartite.


Comments: Authored by O. Goldreich and D. Ron. Appeared in



Oded Goldreich
2003-07-30