Testing Bipartiteness in Logarithmic Rounds

Abstract

The seminal work of Goldreich and Ron (\textit{Combinatorica, 1999}) showed that bipartiteness of bounded-degree graphs can be tested using $O(\sqrt{n\log n})$ random walks of length $O({\log }^{6}n)$. In this work, we improve their result by showing that $O(\sqrt{n})$ random walks of length $O(\log n)$ suffice. As a corollary, we obtain an $O(\log n)$-pass, $O(\sqrt{n}\log n)$-space streaming algorithm for testing bipartiteness, whose pass complexity is optimal in light of a recent lower bound of Fei, Minzer, and Wang (\textit{arXiv, 2026}). Our proof takes a different approach from that of Goldreich and Ron, using the semidefinite programming relaxation for Max-Cut introduced by Goemans and Williamson (\textit{J. ACM, 1995}).