A sublinear bipartiteness tester for bounded degree graphs (Q1964592)

We present a sublinear-time algorithm for testing whether a bounded degree graph is bipartite or far from being bipartite. Graphs are represented by incidence lists of bounded length and the testing algorithm can perform queries of the form ``who is the \(i\)th neighbour of vertex \(v\)''. The tester should determine with high probability whether the graph is bipartite or \(\varepsilon\)-far from bipartite for any given distance parameter \(\varepsilon\). Distance between graphs is defined to be the fraction of entries on which the graphs differ in their incidence-lists representation.'' Their algorithm uses random walk technique and its performance is tight (in a sense explained in the paper).