[May 16, 2010] Andrej Bogdanov A better tester for bipartiteness? Abstract: Alon and Krivelevich showed that if a graph is $\epsilon$-far from bipartite, then a subgraph induced by a random subset of about $1/\epsilon$ vertices is likely to contain an odd length cycle. We conjecture that this subgraph is likely to be far from bipartite. We prove the conjecture is true for regular graphs of any degree. Assuming this conjecture, we give an algorithm that tests bipartiteness in time $O((1/\epsilon)^{2-c})$, where $c > 0$ is some universal constant. Our algorithm is inherently adaptive, as it is known that non-adaptive algorithms for testing bipartiteness require at least $(1/\epsilon)^2$ queries. Based on joint work with Li Fan.