pith. sign in

arxiv: 2606.13583 · v1 · pith:EMSMFZ5Jnew · submitted 2026-06-11 · 💻 cs.DS

Testing Bipartiteness in Logarithmic Rounds

Yumou Fei , Ronitt Rubinfeld This is my paper

Pith reviewed 2026-06-27 04:48 UTC · model grok-4.3

classification 💻 cs.DS
keywords bipartiteness testingproperty testingrandom walksbounded degree graphsstreaming algorithmsgraph algorithms
0
0 comments X

The pith

Bipartiteness of bounded-degree graphs can be tested with O(√n) random walks of length O(log n)

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper shows that testing bipartiteness in bounded-degree graphs requires only O(√n) random walks of length O(log n). Prior work needed a logarithmic factor more walks and walks that were much longer. The improvement follows from a tighter analysis of how the walks interact with the graph's distance to bipartiteness. This matters because fewer and shorter walks reduce the resources required for property testing on large graphs. The same analysis also produces a streaming algorithm whose number of passes matches a known lower bound.

Core claim

O(√n) random walks of length O(log n) suffice to test bipartiteness of bounded-degree graphs. The proof adapts a vector relaxation of the maximum cut problem to show that the walks detect odd cycles with high probability whenever the input graph is far from bipartite.

What carries the argument

Adaptation of a vector relaxation for the maximum cut problem, used to bound the probability that random walks detect violations of bipartiteness.

If this is right

  • The same bound yields an O(log n)-pass streaming algorithm that uses O(√n log n) space.
  • The streaming algorithm's pass complexity is optimal because it matches an existing lower bound.
  • Both the number of walks and the length of each walk are reduced relative to earlier analyses.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same relaxation technique might improve query bounds for testing other properties such as the absence of short cycles.
  • Logarithmic-length walks may suffice for a wider range of local exploration tasks once similar bounds are derived.
  • The gap between the new upper bound and information-theoretic lower bounds on the number of walks could be closed by tighter analysis.

Load-bearing premise

The vector relaxation of the maximum cut problem supplies a bound strong enough to guarantee that random walks detect non-bipartiteness with constant probability.

What would settle it

A bounded-degree graph far from bipartite on which O(√n) walks of length O(log n) succeed in detecting the violation with probability less than a fixed constant.

read the original 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}).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper improves the Goldreich-Ron bipartiteness tester for bounded-degree graphs: it shows that O(√n) random walks of length O(log n) suffice to distinguish bipartite graphs from those ε-far from bipartite (with constant probability), improving the prior O(√n log n) walks of length O(log^6 n). The proof adapts the Goemans-Williamson SDP relaxation for Max-Cut to analyze collision probabilities of short random walks. A corollary is an O(log n)-pass, O(√n log n)-space streaming algorithm whose pass complexity matches a recent lower bound.

Significance. If correct, the result tightens the query complexity of a canonical property-testing problem and yields the first optimal-pass streaming algorithm for bipartiteness. The use of the GW SDP to control walk collisions is a technically interesting departure from the combinatorial analysis in prior work.

major comments (2)
  1. [Proof of Theorem 1.1 (or equivalent)] The central claim that the GW vector embedding directly yields an O(log n) walk length without extra logarithmic factors (via collision probabilities) is load-bearing; the manuscript must explicitly derive the collision bound from the SDP value in the ε-far case and show why local correlations in bounded-degree graphs do not force an additional log factor. Cite the relevant theorem or lemma that converts the SDP gap into the required probability statement.
  2. [Section 3 (SDP adaptation)] The analysis must address whether the random-walk collision test inherits the same approximation guarantees as the GW rounding or whether the embedding-to-walk reduction introduces a dependence on maximum degree or ε that is hidden in the O(log n) notation.
minor comments (2)
  1. [Theorem 1.1] Clarify the precise dependence on ε in the number of walks and walk length; the abstract states O(√n) and O(log n) but the dependence should be stated explicitly.
  2. [Section 4] The streaming corollary should include a brief comparison table with the Fei-Minzer-Wang lower bound to make the optimality claim immediate.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback. The comments correctly identify places where the SDP analysis requires more explicit detail. We will revise the manuscript to address both points.

read point-by-point responses

  1. Referee: [Proof of Theorem 1.1 (or equivalent)] The central claim that the GW vector embedding directly yields an O(log n) walk length without extra logarithmic factors (via collision probabilities) is load-bearing; the manuscript must explicitly derive the collision bound from the SDP value in the ε-far case and show why local correlations in bounded-degree graphs do not force an additional log factor. Cite the relevant theorem or lemma that converts the SDP gap into the required probability statement.

    Authors: We agree the derivation must be made fully explicit. The current manuscript sketches the argument via the SDP value but does not contain the requested step-by-step conversion from SDP gap to collision probability. In the revision we will insert a new lemma (placed after the SDP formulation) that derives the bound: when the graph is ε-far from bipartite the SDP optimum is at most 1−Ω(ε), which implies that the expected inner-product term forces a collision probability of Ω(1) already for walks of length O(log n). The proof that no extra logarithmic factor arises from local correlations proceeds by noting that bounded degree implies the graph is locally tree-like up to distance log n, yet the global vector assignment ensures that any two walks that reach opposite sides of the cut have inner product close to −1; the collision probability is therefore controlled directly by the SDP gap without requiring additional mixing-time factors. We will cite the relevant statement from Goemans–Williamson (J. ACM 1995, Thm. 2) together with the adaptation to collision probabilities. revision: yes

  2. Referee: [Section 3 (SDP adaptation)] The analysis must address whether the random-walk collision test inherits the same approximation guarantees as the GW rounding or whether the embedding-to-walk reduction introduces a dependence on maximum degree or ε that is hidden in the O(log n) notation.

    Authors: The collision test does not inherit the 0.878-approximation guarantee of GW rounding; it uses only the vector embedding to bound collision probabilities and therefore operates with a different (weaker) guarantee tied directly to the SDP value gap. The embedding-to-walk reduction introduces no hidden dependence on maximum degree (constant by assumption) or on ε beyond the usual dependence already present in the definition of ε-far. The walk length remains O(log n) with the implicit constant independent of both d and ε. In the revision we will add a clarifying paragraph in Section 3 stating these facts explicitly and confirming that the O(log n) notation does not conceal any such dependence. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation relies on external 1995 GW SDP and independent lower bound

full rationale

The paper explicitly contrasts its approach with Goldreich-Ron and states it uses the Goemans-Williamson SDP relaxation (JACM 1995) as the proof technique. This is an external, long-established result unrelated to the authors. The only self-citation is the 2026 lower bound of Fei-Minzer-Wang used solely to establish optimality of the derived streaming algorithm, not to justify the bipartiteness tester itself. No equations, ansatzes, or predictions in the provided text reduce to self-definition or fitted inputs; the claimed O(log n) walk length is presented as following from the SDP analysis rather than being presupposed.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review performed on abstract only; the central claim rests on the unshown adaptation of the Goemans-Williamson SDP to random-walk analysis for bipartiteness. No free parameters or invented entities are mentioned in the abstract.

axioms (1)
  • domain assumption The Goemans-Williamson SDP relaxation for Max-Cut can be used to obtain improved bounds on random walks for bipartiteness testing.
    Abstract states that the proof uses this SDP relaxation.

pith-pipeline@v0.9.1-grok · 5682 in / 1174 out tokens · 34549 ms · 2026-06-27T04:48:31.488169+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

30 extracted references · 1 canonical work pages

  1. [1]

    arXiv preprint arXiv:2502.18382 , year=

    Property Testing in Bounded Degree Hypergraphs , author=. arXiv preprint arXiv:2502.18382 , year=

    arXiv

  2. [2]

    Proceedings of the ACM Web Conference 2023 , pages=

    Testing cluster properties of signed graphs , author=. Proceedings of the ACM Web Conference 2023 , pages=

    2023

  3. [3]

    and Montanaro, Ashley , title =

    Tugkan Batu and Lance Fortnow and Ronitt Rubinfeld and Warren D. Smith and Patrick White , title =. J. 2013 , url =. doi:10.1145/2432622.2432626 , timestamp =

    work page doi:10.1145/2432622.2432626 2013

  4. [4]

    The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002

    A lower bound for testing 3-colorability in bounded-degree graphs , author=. The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. , pages=. 2002 , organization=

    2002

  5. [5]

    ACM Transactions on Algorithms (TALG) , volume=

    Near-optimal algorithms for maximum constraint satisfaction problems , author=. ACM Transactions on Algorithms (TALG) , volume=. 2009 , publisher=

    2009

  6. [6]

    2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Testing graph clusterability: Algorithms and lower bounds , author=. 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2018 , organization=

    2018

  7. [7]

    Combinatorics, Probability and Computing , volume=

    Testing expansion in bounded-degree graphs , author=. Combinatorics, Probability and Computing , volume=. 2010 , publisher=

    2010

  8. [8]

    Random Structures & Algorithms , volume=

    Finding cycles and trees in sublinear time , author=. Random Structures & Algorithms , volume=. 2014 , publisher=

    2014

  9. [9]

    Proceedings of the forty-seventh annual ACM symposium on Theory of Computing , pages=

    Testing cluster structure of graphs , author=. Proceedings of the forty-seventh annual ACM symposium on Theory of Computing , pages=

  10. [10]

    1st Symposium on Simplicity in Algorithms , year=

    On Sampling Edges Almost Uniformly , author=. 1st Symposium on Simplicity in Algorithms , year=

  11. [11]

    SIAM Journal on Computing , volume=

    The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory , author=. SIAM Journal on Computing , volume=. 1998 , publisher=

    1998

  12. [12]

    A dichotomy theorem for multi-pass streaming

    Fei, Yumou and Minzer, Dor and Wang, Shuo , journal=. A dichotomy theorem for multi-pass streaming

  13. [13]

    Unbounded-width

    Fei, Yumou , journal=. Unbounded-width

  14. [14]

    Near-Optimal Space Lower Bounds for Streaming

    Fei, Yumou and Minzer, Dor and Wang, Shuo , journal=. Near-Optimal Space Lower Bounds for Streaming

  15. [15]

    arXiv preprint arXiv:2603.22702 , year=

    Testing Properties of Edge Distributions , author=. arXiv preprint arXiv:2603.22702 , year=

    arXiv

  16. [16]

    Journal of the ACM (JACM) , volume=

    Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming , author=. Journal of the ACM (JACM) , volume=. 1995 , publisher=

    1995

  17. [17]

    Combinatorica , volume=

    A Sublinear Bipartiteness Tester for Bounded Degree Graphs , author=. Combinatorica , volume=. 1999 , publisher=

    1999

  18. [18]

    Algorithmica , volume=

    Property Testing in Bounded Degree Graphs , author=. Algorithmica , volume=. 2002 , publisher=

    2002

  19. [19]

    Studies in Complexity and Cryptography , pages=

    On Testing Expansion in Bounded-Degree Graphs , author=. Studies in Complexity and Cryptography , pages=. 2011 , publisher=

    2011

  20. [20]

    51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) , pages=

    A sublinear time tester for Max-Cut on clusterable graphs , author=. 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) , pages=. 2024 , organization=

    2024

  21. [21]

    SIAM Journal on Computing , volume=

    An expansion tester for bounded degree graphs , author=. SIAM Journal on Computing , volume=. 2011 , publisher=

    2011

  22. [22]

    SIAM Journal on computing , volume=

    Tight bounds for testing bipartiteness in general graphs , author=. SIAM Journal on computing , volume=. 2004 , publisher=

    2004

  23. [23]

    Optimal inapproximability results for

    Khot, Subhash and Kindler, Guy and Mossel, Elchanan and O’Donnell, Ryan , journal=. Optimal inapproximability results for. 2007 , publisher=

    2007

  24. [24]

    Random Walks and Forbidden Minors

    Kumar, Akash and Seshadhri, C and Stolman, Andrew , journal=. Random Walks and Forbidden Minors. 2020 , publisher=

    2020

  25. [25]

    Information and Computation , volume=

    Testing the expansion of a graph , author=. Information and Computation , volume=. 2010 , publisher=

    2010

  26. [26]

    Proceedings of the fortieth annual ACM symposium on theory of computing , pages=

    An optimal. Proceedings of the fortieth annual ACM symposium on theory of computing , pages=

  27. [27]

    Sublinear-time algorithms for

    Peng, Pan and Yoshida, Yuichi , booktitle=. Sublinear-time algorithms for. 2023 , organization=

    2023

  28. [28]

    IEICE TRANSACTIONS on Information and Systems , volume=

    Query-number preserving reductions and linear lower bounds for testing , author=. IEICE TRANSACTIONS on Information and Systems , volume=. 2010 , publisher=

    2010

  29. [29]

    Lower bounds on query complexity for testing bounded-degree

    Yoshida, Yuichi , booktitle=. Lower bounds on query complexity for testing bounded-degree. 2011 , organization=

    2011

  30. [30]

    Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree

    Yoshida, Yuichi , booktitle=. Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree