Testing Bipartiteness in Logarithmic Rounds

The seminal work of Goldreich and Ron ($\mathit{\text{Combinatorica,}}\mathit{\text{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 ($\mathit{\text{arXiv,}}\mathit{\text{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 ($\mathit{\text{J.}}\mathit{\text{ACM,}}\mathit{\text{1995}}$).