Undirected Connectivity in Log-Space
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, 2005 · paper · Computer science
Presents a deterministic log-space algorithm for deciding whether two vertices in an undirected graph are connected, which implies SL = L. It also yields log-space constructible universal-traversal and universal-exploration sequences.
Checked: PDF from omereingold.wordpress.com, fetched 4 Oct 2026. Page numbers are those of that PDF.
3 findings
Substance Proof of Lemma 3.2 applies Lemma 2.5 to G as if it were D-regular ("λ(G0) ≤ 1 − 1/DN²"), but by Definition 3.1 G is D¹⁶-regular, so Lemma 2.5 gives only λ(G0) ≤ 1 − 1/(D¹⁶N²). The choice "ℓ = 2⌈log DN²⌉" is based on the stronger bound and is too small for small N.
- p. 7 Lemma 2.5
λ(G) ≤ 1 − 1/DN².
- p. 10 Definition 3.1
Set ℓ = 2⌈log DN²⌉.
- p. 10 Proof of Lemma 3.2, first sentence
λ(G₀) ≤ 1 − 1/DN².
- p. 10 Proof of Lemma 3.2, first sentence
we have by Lemma 2.5 that λ(G0) ≤1 −1/DN2
Only the authors can say what is right here.
Judge's note: Checked p.7 (Lemma 2.5, stated for a generic D-regular graph) and p.10 (Definition 3.1: G is D¹⁶-regular on [N], H is D-regular on [D¹⁶]; proof of Lemma 3.2 writes λ(G0) ≤ 1 − 1/DN²). My own reworking: take N=2 and q=D¹⁶. Let G have one edge between vertices 1 and 2 and q−1 self-loops at each vertex. It is connected, non-bipartite and q-regular, and its normalized matrix [[1−1/q,1/q],[1/q,1−1/q]] has eigenvalues 1 and 1−2/q. For D≥2, 2/q < 1/(4D), so λ(G0) > 1 − 1/(DN²). The bound the proof uses is false for this G. Lemma 2.5 applied with the true degree q (1−1/(4q)) does hold, so the lemma was misapplied. Lower bound on later phases: let f be g⊗1 with g=(1,−1). Steps inside a cloud fix f, so the Rayleigh quotient of the zig-zag matrix at f equals λ(G). Hence λ(G_i ⓩ H) ≥ λ(G_i) and λ(G_ℓ) ≥ λ(G0)^(8^ℓ). With D=16 (a degree for which a (D¹⁶,D,1/2)-graph is plausible by the Alon–Boppana bound), the printed ℓ is 2·6=12, and λ(G_ℓ) ≥ 1 − 2·8¹²/16¹⁶ ≈ 1 − 2⁻²⁷ > 1/2. So with the printed ℓ, Lemma 3.2's conclusion fails whenever such an H exists. One reviewer argued that D≥5 suffices for H to exist; I did not rely on that. The fix (ℓ = 2⌈log D¹⁶N²⌉) is still O(log N) for constant D, so Theorem 4.1 is unaffected. Even so, Lemma 3.2 is false as printed with the ℓ of Definition 3.1, so I rate it S1.
Second check: another model agreed
Report a problem with this finding
Reference or label Proof of Lemma 5.2, p.14: "Consider the log-space algorithm Aτ in the proof of Theorem 3.4" — Aτ is defined in the proof of Lemma 3.4; there is no Theorem 3.4.
- p. 14 Proof of Lemma 5.2, first sentence
Consider the log-space algorithm Aτ in the proof of Theorem 3.4
- p. 11 Lemma 3.4
Lemma 3.4 For every constant D the transformation T of Definition 3.1 can be computed in space O(log N)
- p. 14 Proof of Lemma 5.2
algorithm Aτ in the proof of Theorem 3.4
- p. 14 Proof of Lemma 5.2
in the proof of Theorem 3.4
Judge's note: Page 11 shows 'Lemma 3.4' with the proof that defines A_τ. Page 13 and Appendix A (text line 1083) both refer to it as Lemma 3.4. The page 14 crop shows the cross-reference printed as 'Theorem 3.4'.
Second check: another model agreed
Report a problem with this finding
Wording Proof of Theorem 5.4 (p.15) reads "Finally let G_ℓ = T(G, H)", but in this proof G is the original D-regular graph. The D_e^16-regular graph G′ just introduced is the input that fits Definition 3.1, so it should read T(G′, H).
- p. 15 Proof of Theorem 5.4, last paragraph
Finally let Gℓ= T (G, H), where T and ℓare
Judge's note: On p.15, the first paragraph of the proof defines G as a connected D-regular graph on N vertices and G′ as the D_e^16-regular graph on N·D vertices. The paragraph in question opens with "Now we consider a D_e^16-regular ... graph G′" and goes on to talk about vertices and labels of G′. Definition 3.1 / Lemma 3.4 (p.11) need a D^16-regular input G, so T(G,H) here is a symbol slip for T(G′,H).
Second check: another model agreed
Report a problem with this finding
24 minor (typos and the like; most checked by the judge only)
Reference or label Reference [ATSWZ00] prints the title as "An o(log(n)^{4/3}) space algorithm ..." with a little-o, while the abstract ("log^{4/3}(·)") and introduction ("USTCON ∈ L^{4/3}") describe the result as a log^{4/3} bound.
- p. 19 Reference [ATSWZ00]
An o(log(n)4/3) space
- p. 2 Introduction
showed that USTCON ∈L4/3
- p. 19 Reference list, [ATSWZ00]
An o(log(n)4/3) space algorithm for (s,t) connectivity in undirected graphs
- p. 1 Abstract
The previous bound on the space complexity of undirected st-connectivity was log4/3(·)
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: the published title of the cited JACM paper uses a capital O. The page 19 image shows a math-italic lowercase o. The page 1 and 2 images give the bound as log^{4/3} / L^{4/3}. This is probably BibTeX lower-casing of the title.
Second check: another model agreed
Report a problem with this finding
Reference or label Reference [Tri05] title reads "An o(log n log log n) space algorithm for undirected s,t-connectivity", while the abstract and introduction both say "an O(log n log log n)-space, deterministic algorithm".
- p. 22 Reference [Tri05]
An o(log n log log n) space algorithm for undirected s,t-connectivity
- p. 1 Abstract
O(log n log log n)-space, deterministic algorithm
- p. 1 Abstract
an O(log n log log n)-space, deterministic algorithm for undirected st-connectivity
- p. 2 Introduction
Trifonov [Tri05] has presented an O(log n log log n)-space
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: Trifonov's published STOC title uses a capital O. The page 22 image shows a lowercase 'o' in the reference, and the page 1 and 2 crops show O(·). This is probably case-folding in the bibliography.
Second check: another model agreed
Report a problem with this finding
Reference or label Reference [NSW89] prints the title as "Undirected connectivity in o(log^{1.5} n) space" with a little-o, while the introduction credits NSW89 with "USTCON ∈ L^{3/2}".
- p. 21 Reference list, [NSW89]
Undirected connectivity in o(log1.5n) space
- p. 2 Introduction
[NSW89] who showed that USTCON ∈L3/2
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: the published FOCS title uses a capital O. The image of the p.21 reference shows a math-italic lowercase o, and the p.2 crop shows L^{3/2}. This is probably BibTeX case-folding. It is a separate reference from C023 and C028.
Second check: another model agreed
Report a problem with this finding
Reference or label Reference [BNS89] is given as a journal article ("Journal of Computer and System Sciences, pages 204–232, 15–17 May 1989.") with no volume and with a conference date range identical to the STOC 1989 dates in [FKS89].
- p. 19 Reference [BNS89]
Journal of Computer and System Sciences, pages 204–232, 15–17 May 1989.
- p. 19 Reference list, [FKS89]
Seattle, Washington, 15–17 May 1989.
Only the authors can say what is right here.
Judge's note: Page 19 image confirms the entry text, and that [FKS89] gives the STOC 1989 dates as "15–17 May 1989". The entry mixes journal and conference details. Rests on outside knowledge: the actual JCSS volume and year of the journal version, which only the authors or the source can settle.
Second check: another model agreed
Report a problem with this finding
Reference or label [YBAS95] is cited as "Information and Computation, 21(1):41–58, 1995"; a 1995 article in that journal would be in a volume around 121, not 21.
- p. 22 References, [YBAS95]
Information and Computation, 21(1):41–58, 1995
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: the claim that Information and Computation volumes in 1995 were numbered around 121, and that this article (Ben-Asher, Lange, Peleg, Schuster, "The complexity of reconfiguring network models") appeared in 121(1):41–58. The crop and page 22 show the entry exactly as quoted, with "21(1)". The files cannot settle the true volume, so this is a query for the authors.
Second check: another model agreed
Report a problem with this finding
Wording Intro p.3: "Each phase starts by raising the current graph to some constant power and then reducing the degree back via a replacement or a zig-zag product", whereas Definition 3.1 sets G_i = (G_{i-1} ⓩ H)^8 (zig-zag first, then powering).
- p. 3 Introduction, algorithm overview
Each phase starts by raising the current graph to some constant power and then reducing the degree back via a replacement or a zig-zag product
- p. 10 Definition 3.1
Gi = (Gi−1⃝z H)8
Judge's note: Both images confirm the opposite order. The overview is informal and the operations alternate, so the effect is small. Still, the intro's description of one phase does not match the formal phase in Definition 3.1, which starts from the D^16-regular G, applies the zig-zag product with H and then raises to the 8th power.
Second check: another model agreed
Report a problem with this finding
Wording Lemma 3.3 states "T(G|S, H) = T(G, H)|S×([D¹⁶])ℓ". But T, as defined, picks its number of phases from the vertex count of its input ("Set ℓ = 2⌈log DN²⌉"). The proof only shows T_i(G|S,H) = T_i(G,H)|S×([D¹⁶])^i for one common i.
- p. 10 Definition 3.1
Set ℓ = 2⌈log DN²⌉.
- p. 10 Lemma 3.3
T(G|S, H) = T(G, H)|S×([D¹⁶])ℓ.
- p. 11 Proof of Lemma 3.3, conclusion
This proves the induction hypothesis for i + 1 and completes the proof.
- p. 10 Proof of Lemma 3.3
will prove inductively that Ti(G|S, H) = Ti(G, H)|S×([D16])i
Only the authors can say what is right here.
Judge's note: Checked p.10 (Definition 3.1 and Lemma 3.3), p.11 (the induction) and p.13 (Theorem 4.1 uses G_exp|… = T(G_reg|S×[N], H) and then applies Lemma 3.2). The induction is correct for a common number of phases i. Read literally, T(G|S,H) uses ℓ_S = 2⌈log D|S|²⌉, which is smaller than ℓ when |S| < N, so the two sides have different vertex sets. G|S is also a graph on S rather than on [N'], so Definition 3.1 does not apply to it without relabelling. The intended reading (use the ambient ℓ) is suggested by the subscript ℓ on the right-hand side. The recursion λ(G_i) ≤ max{λ(G_{i−1})², 1/2} shows that extra phases keep λ ≤ 1/2, so Theorem 4.1 stands. This is an imprecision in the statement, not a failed result.
Second check: another model agreed
Report a problem with this finding
Wording The Appendix A algorithm has no transition for an even j_I < 16. After step 2 ("Set jI ← jI + 1 and go to Step (1)") or step 6, step 1 runs with an even j_I, and then none of steps 2–6 (j_I odd, or "If jI = 16") applies, so the procedure neither continues nor outputs.
- p. 22 Appendix A, steps 1-3
If jI is odd, and I = 1 set v, a0 ←RotG(v, a0)
- p. 23 Appendix A, steps 4-6
If jI = 16 and I < ℓ, set jI+1 ←jI+1 + 1 and I ←I + 1. Go to Step (1).
- p. 11 Proof of Lemma 3.4, loop
For j = 1 to 16
- p. 22 Appendix A, algorithm Step 2
Set jI ← jI + 1 and go to Step (1).
Only the authors can say what is right here.
Judge's note: Checked pp.22–23. Steps 2–3 require j_I odd; steps 4–6 require j_I = 16. Trace: I=1, j1=1 → step 1 (H step) → step 2 (Rot_G, j1=2, go to step 1) → step 1 (H step for j=2) → no step applies. The same happens after step 6, which makes j_{I+1} even. The recursive description on p.11 ("For j = 1 to 16 … If j is odd, recursively …") does an H step for every j, so the appendix is missing a branch such as 'if j_I is even and j_I < 16, set j_I ← j_I+1 and go to Step (1)'. Lemma 3.4 rests on the main-text description and still stands.
Second check: another model agreed
Report a problem with this finding
Typo Footnote 1, p.2: "we will (somewhat cheatingly) elude to a definition based on vertex expansion" — 'elude' (evade) should be 'allude'.
- p. 2 Footnote 1
(somewhat cheatingly) elude to a definition
- p. 2 Footnote 1
(somewhat cheatingly) elude to a definition based on vertex expansion
- p. 8 Section 2.4
significantly smaller that D
- p. 2 footnote 1
will (somewhat cheatingly) elude to
Judge's note: The page image shows 'elude to' in footnote 1. The same footnote also prints 'knowledgable', which should be 'knowledgeable'. The 'smaller that D' part of this cluster (p.8) is judged on its own under C006.
Second check: none (judge only)
Report a problem with this finding
Typo p.4, Universal traversal sequences paragraph: "constructible in logartihmic space (even less explicit ..." — misspelling of 'logarithmic'.
- p. 4 Universal traversal sequences paragraph
constructible in logartihmic space
- p. 4 Introduction, Universal traversal sequences paragraph
constructible in logartihmic space (even
- p. 4 Introduction, Universal traversal sequences paragraph
constructible in logartihmic
Judge's note: The misspelling is printed on the page image (first occurrence). The second occurrence, further down page 4, is cluster C005.
Second check: none (judge only)
Report a problem with this finding
Typo p.4: "universal-traversal sequence that is constructible in logartihmic space under some restrictions on the labeling" — misspelling of 'logarithmic' (second occurrence).
- p. 4 Universal traversal sequences, para 2
constructible in logartihmic
- p. 4
constructible in logartihmic space under some restrictions on the labeling
Judge's note: The page image shows a second, separate occurrence of the misspelling, in the paragraph just before 'More on previous work'. It is a distinct instance from C004.
Second check: none (judge only)
Report a problem with this finding
Typo Section 2.4, p.8: "(which should still be thought of as significantly smaller that D)" — 'that' should be 'than'.
- p. 8 Section 2.4, first paragraph
significantly smaller that D
Judge's note: Confirmed on the page 8 image. Earlier in the same paragraph the paper correctly writes 'significantly smaller than D'.
Second check: none (judge only)
Report a problem with this finding
Typo Proof of Theorem 4.1, p.12: "Furthermore, G will use space which is logarithmic in its input size." — the subject should be the algorithm A_con, not the input graph G.
- p. 12 Proof of Theorem 4.1, first paragraph
Furthermore, G will use space which is logarithmic in its input size.
- p. 12 Proof of Theorem 4.1, first paragraph
Furthermore, G will use space which is logarithmic in
- p. 12 Proof of Theorem 4.1, first paragraph
Furthermore, G will use space which is logarithmic
Judge's note: Confirmed on the page 12 image. G is defined in the preceding sentence as the input graph, and the space claim is about the algorithm A_con. The intended meaning is clear from context, so this is a slip.
Second check: none (judge only)
Report a problem with this finding
Typo Proof of Theorem 4.1, p.13: "Let Aexp be the the algorithm guaranteed by Proposition 2.3" — duplicated 'the'.
- p. 13 Proof of Theorem 4.1
Let Aexp be the the algorithm
- p. 13
omponent of Gexp. Let Aexp be the the algorithm guarantee
Judge's note: Confirmed on the page 13 image. Page 14 has similar duplications ('and the the first element of', 'that the the only way'), but those are outside this cluster's quote.
Second check: code check
Report a problem with this finding
Typo p.13: "the connected component of the starting vertex is an expanders" — should be 'an expander'.
- p. 13 Proof of Theorem 4.1
the connected component of the starting vertex is an expanders
- p. 13 Proof of Theorem 4.1
is an expanders
Judge's note: Confirmed on the page 13 image.
Second check: none (judge only)
Report a problem with this finding
Typo Section 5, p.13: "finding the path from s to t if such a path exist" — should be 'exists'.
- p. 13 Section 5, first paragraph
if such a path exist)
- p. 13 Section 5 intro
if such a path exist
Judge's note: Confirmed on the page 13 image. Elsewhere (pp.1, 12, 14) the paper writes 'if such a path exists'.
Second check: none (judge only)
Report a problem with this finding
Typo Duplicated word on p.14: Lemma 5.2 statement "and the the first element of Rot_{G_ℓ}(v̄,ā)" and its proof "We note that the the only way Rot_G influences".
- p. 14 Lemma 5.2 statement
and the the first element of
- p. 14 Proof of Lemma 5.2
We note that the the only way
- p. 14 Lemma 5.2 statement
and the the first element
- p. 14
of ¯v is a vertex u ∈[N] and the the first element of Rot
Judge's note: Page 14 image shows both occurrences of "the the", one in the Lemma 5.2 statement and one in the second paragraph of its proof.
Second check: code check
Report a problem with this finding
Typo p.15, proof of Theorem 5.4: "Each vertex v ∈ N is transformed into a cycle" should read v ∈ [N].
- p. 15 Proof of Theorem 5.4
Each vertex v ∈N is transformed into a cycle
Judge's note: The page 15 image prints "v ∈ N" without brackets. Elsewhere the paper writes vertex sets as [N].
Second check: none (judge only)
Report a problem with this finding
Typo The proof of Theorem 5.4 ends with "The lemma follows." (p.16), but the result being proved is a theorem.
- p. 16 End of proof of Theorem 5.4
The lemma follows.
Judge's note: The page 16 image confirms the wording. The statement proved is Theorem 5.4 (p.15). This is cosmetic.
Second check: none (judge only)
Report a problem with this finding
Typo p.16: "we concatenate for each sequences in B′" should read "each sequence".
- p. 16 Proof of Theorem 5.4, continued
we concatenate for each sequences in B′
Judge's note: Confirmed on the page 16 image, first line.
Second check: none (judge only)
Report a problem with this finding
Typo p.18: "An example of oblivious derandomiztion is derandomiztion by pseudorandom generators" has 'derandomization' misspelled twice.
- p. 18 Section 6, final paragraph
An example of oblivious derandomiztion is derandomiztion by pseudorandom generators
- p. 18 p.18 para 2
An example of oblivious derandomiztion is
Judge's note: The crop of p.18 shows both misspellings.
Second check: none (judge only)
Report a problem with this finding
Typo In [Gol08] the URL is printed "http://www.wisdom.weizmann.ac.il/ oded/cc-drafts.html", with a space where the '~' belongs.
- p. 19 Reference list, [Gol08]
http://www.wisdom.weizmann.ac.il/ oded/cc-drafts.html
Judge's note: The page 19 image shows a space between 'il/' and 'oded/', so this is not an extraction artefact.
Second check: none (judge only)
Report a problem with this finding
Typo Reference [Wig92] has a duplicated word: "In In Proceedings of the 17th Mathematical Foundations of Computer Science".
- p. 22 Reference [Wig92]
In In Proceedings of the 17th Mathe-
- p. 22 Reference list, [Wig92]
In In Proceedings of the 17th Mathematical Foundations of Computer Science
Judge's note: Confirmed on the page 22 image.
Second check: none (judge only)
Report a problem with this finding
Typo The [YBAS95] author list is printed "D. Peleg Y. Ben-Asher, K. Lange and A. Schuster.", with Peleg placed first and no separator, which conflicts with the key YBAS and the text's "Ben Asher et. al. [YBAS95]".
- p. 22 Reference [YBAS95]
D. Peleg Y. Ben-Asher, K. Lange and A. Schuster.
Judge's note: The page 22 image shows the garbled order, and p.2 of the text cites it as 'Ben Asher et. al.'. A reviewer also suggested the volume (21) is wrong for 1995. That claim rests on outside knowledge and cannot be checked from the files, so it is not part of this confirmation.
Second check: none (judge only)