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ē queries. Our conjecture and algorithm build upon previous works on testing bipartiteness by Alon and Krivelevich, Goldreich and Ron, and Gonen and Ron. Based on joint work with Li Fan.