Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

• p. 70 Proof of Lemma 8.3, WIN cost

  Crm/ki (Line 6)

• p. 70 Proof of Lemma 8.3, LOSS cost

  LOSS at some level i (Line 10)

• p. 65 Algorithm 6

  Fix level i, thus rebuilding levels j ≥i.

Judge's note: Page 65 image shows Algorithm 6: Line 6 is 'Find the smallest level i', Line 7 is 'Fix level i'; Line 10 is 'Let i be the smallest level', Line 11 is 'Fix level i'. The page 69 outline uses the same Line 6/10 references. Lines 6/10 start the WIN/LOSS blocks, so the reference is loose rather than clearly wrong.

Second check: another model agreed

• p. 4 Section 1

  B((a,b),v) is 1 if v = a, −1 if v = b

• p. 95 Appendix B.1

  dv > dv, then add an edge ev = (v →v∗) with upper capacity 2(dv −dv)

• p. 105 Proof of Lemma C.9

  If fe = 0, we set s− e = ce −(yv −yu)

Only the authors can say what is right here.

Judge's note: Section 1 (p.4) defines the matrix so that (B^T f)_v = outflow − inflow and (By)_(u,v) = y_u − y_v. B.1 (p.95): if d̄_v > d_v, an edge v→v* carrying d̄_v − d_v adds outflow at v, so (B^T f)_v becomes 2d̄_v − d_v, not d_v. Under the Section 1 convention the edge should point v*→v. C.9 (p.105): a valid distance label gives y_v − y_u ≤ c_e, written B(f)y ≤ c(f), so (By)_e = y_v − y_u. That is again the reversed sign. Appendix C only says the matrix 'respects the edge orientation' (p.103) and does not state a sign. Each argument works under the flipped convention, so the results stand. The text is still inconsistent with the definition the paper gives.

Second check: another model agreed

• p. 5 Section 1.1

  p-norm isotonic regression for all p ∈[1, ∞]

• p. 83 Theorem 10.15

  and p ∈[1, ∞], we can compute

• p. 112 Appendix D, Isotonic Regression

  solution to Isotonic regression for all p ∈[1, ∞)

• p. 112 Appendix D, Isotonic Regression

  Isotonic regression for all p ∈ [1, ∞)

Only the authors can say what is right here.

Judge's note: I checked p.5, p.83 and p.112. In Section 1.1 and Theorem 10.15 the range includes ∞. In Appendix D, the sentence stating the paper's own result excludes ∞. The authors need to say whether p = ∞ is covered. One reviewer's 'mismatched brackets' point is wrong: [1, ∞) is standard half-open interval notation, not a typo.

Second check: another model agreed, code check

• p. 5 Section 1.1

  as well as p-norm flow problems and p-norm isotonic regression for all p ∈[1, ∞]

• p. 82 Theorem 10.14

  the sum of eO(1) p-norm terms

Only the authors can say what is right here.

Judge's note: I checked p.5 and Theorem 10.14 on p.82. Theorem 10.14 requires p_i ≤ Õ(1), which excludes p = ∞ and very large p. As written, the range [1, ∞] in Section 1.1 can be read as applying to p-norm flows as well as to isotonic regression. That is broader than the theorem states. The authors should make the scope of the range clear.

Second check: another model agreed

• p. 5 Section 1.1

  m1+o(1) log U log C time algorithms

• p. 110 Appendix D

  can be solved in time m1+o(1) log2 U in bipartite graphs

Only the authors can say what is right here.

Judge's note: I checked p.5 and p.110. The same application gets two different bounds. Appendix D introduces no assumption that costs are bounded by U, which would explain log^2 U. Only the authors can say which bound is intended. The Appendix D sentence also has a duplicated word, 'that the the worker assignment'.

Second check: another model agreed

• p. 7 Informal Theorem 1.6

  undergoing edge updates (inser- tions/deletions/vertex splits)

• p. 34 Theorem 5.1

  consisting only of edge deletions and eO(n) vertex splits

• p. 7 Informal Theorem 1.6

  tions/deletions/vertex splits), maintains a subgraph H

Only the authors can say what is right here.

Judge's note: I checked p.7 and p.34. Section 7 (text layer, around line 4166) says explicitly: 'we cannot simply maintain the spanner ... using Theorem 5.1 which does not support edge insertions'. It handles insertions separately by inserting them naively into the spanner. So the informal statement claims more than the cited theorem gives, though the overall construction does support insertions.

Second check: another model agreed

• p. 17 Section 2.5

  w(f) = 100 · 1 + |L(f)∆(f)|

• p. 44 Section 6, after Definition 6.1

  w(t) = 10 + |ℓ(f (t)) ◦c(t)|

• p. 73 Lemma 9.2

  w(t) = 50 + |ℓ(t) ◦c(t)|

Only the authors can say what is right here.

Judge's note: I checked pages 17, 44 and 73. Section 6 explicitly points to Lemma 9.2 yet uses a different additive constant. Lemma 9.2's stability step uses ε ≤ (1/100)|w|, which relies on its own constant. Section 10 (p.82) also uses 50. The constant is not essential to the argument, but the stated definitions disagree. One value should be used throughout, or the difference should be explained.

Second check: another model agreed

• p. 18 Section 2.5, paragraph after Eq. (6)

  Because each recomputation reduces the ℓ1 norm of the width by a constant factor, and all the widths are bounded by exp(logO(1) m)

• p. 18 Section 2.5, paragraph after (6)

  Because each recomputation reduces the ℓ1 norm of the width by a constant factor

Judge's note: Checked the crop and p.18. The trigger condition in the previous sentence is a 100-fold increase of the width. The bound on the number of recomputations uses the upper cap exp(log^{O(1)} m) on the widths, and that cap only gives Õ(1) recomputations if the norm grows by a constant factor each time. "Reduces" contradicts this. The passage is in the informal overview, and the evident fix is "increases", so this is a wording error rather than a substantive one.

Second check: another model agreed

• p. 29 Proof of Lemma 4.5, Taylor bound

  ≤φ(fe) + φ′(fe)∆e + 1.3φ′′(fe)∆2

• p. 29 Proof of Lemma 4.5, Taylor chain

  φ(fe) + φ′(fe)∆e + 1.3φ′′(fe)∆2

• p. 29 Proof of Lemma 4.5

  ≤ φ(fe) + φ′(fe)∆e + 1.3φ′′(fe)∆2 e

Only the authors can say what is right here.

Judge's note: Checked on page image p029. The paper gives φ''(x) = α(1+α)((u⁺−x)^{−2−α} + (x−u⁻)^{−2−α}). The middle term 1.3φ''(f_e)Δ² therefore equals 1.3α(1+α)(…)Δ², which is strictly larger than α(…)Δ² whenever Δ_e ≠ 0, so the second '≤' fails. If the ½ is kept, ½·1.3·α(1+α) = 0.65α(1+α) ≤ α for small α, so (13) still holds. The step is wrong but the stated result stands.

Second check: another model agreed

• p. 29 Proof of Lemma 4.4, first display

  ≤2ε/κ · |eg⊤∆| ≤eg⊤∆/2,

• p. 30 Proof of Lemma 4.4

  the final inequality follows from ε ≤κ/8

Only the authors can say what is right here.

Judge's note: Checked p029 to p030 and the statement of Lemma 4.4 on p028. The lemma's hypothesis is ‖L(f)^{-1}(g̃−g(f))‖∞ ≤ κ/8 and it has no ε. Since g̃⊤Δ ≤ −κ‖L̃Δ‖₁ < 0, the right-hand side g̃⊤Δ/2 is negative and cannot bound an absolute value; the intended bound is |g̃⊤Δ|/2. With ε = κ/8 the chain gives (1/4)|g̃⊤Δ| ≤ |g̃⊤Δ|/2, and (17) follows from that, so the lemma stands.

Second check: another model agreed

• p. 30 Proof of Lemma 4.4, bound on |c⊤Δ̄|

  20m · 4η/κ|eg⊤∆| ≤ κ 500m

• p. 30 Display after (20)

  · 4η/κ|eg⊤∆| ≤

Only the authors can say what is right here.

Judge's note: Checked p030 and Lemma 4.4 on p028, which chooses η with ηg̃⊤Δ = −κ²/50. Then (1/(20m))·(4/κ)·(κ²/50) = κ/(250m), so the printed κ/(500m) is half of what the displayed steps give. The κ/(500m) then feeds the term 20m(κ/500m)². Redoing it with κ/(250m) gives a term κ²/(3125m), and the final ≤ −κ²/500 still holds, so the lemma is unaffected.

Second check: another model agreed

• p. 32 Proof of Lemma 4.9

  e −fe)1+α = ε(u+

• p. 32

  (0, 1/2], and

Only the authors can say what is right here.

Judge's note: Checked p032. Because 0 < u⁺−f ≤ 2U, (u⁺−f)^{1+α} = (u⁺−f)(u⁺−f)^α ≤ (u⁺−f)(2U)^α, with equality only when u⁺−f = 2U. The chain holds with ≤, so the lemma stands. The other note in this cluster, about the 'mismatched brackets' in "(0, 1/2]", is not a defect: it is standard half-open interval notation.

Second check: another model agreed, code check

• p. 35 Theorem 5.3

  an embedding Π0 of vertex-congestion at most 2γc∆max(G)

• p. 38 Proof of Claim 5.7, base case

  has vertex-congestion at most γc∆max(G) by Theorem 5.3

• p. 35 Theorem 5.3

  vertex-congestion at most 2γc∆max(G)

• p. 35

  embedding Π0 of vertex-congestion at most 2γc∆max(G)

Only the authors can say what is right here.

Judge's note: Checked p035 (Theorem 5.3) and p038 (proof of Claim 5.7). The claimed base bound 4^0γc^1Δmax = γcΔmax is half of what Theorem 5.3 delivers. The factor 2 can be absorbed, since γc = exp(O(·)), so the asymptotic results stand. Only the authors can say which constant is intended.

Second check: another model agreed

• p. 40 Proof of Lemma 5.9

  maps edges to paths of length γO(L) c in H by Claim 5.8.

• p. 40 end of proof of Lemma 5.9

  paths of length γO(L) c in H by Claim 5.8

• p. 40 Proof of Lemma 5.9, D(t) bound

  maps edges to paths of length

Only the authors can say what is right here.

Judge's note: Checked p.40 (top) and Claim 5.8 on p.39. Claim 5.8 states length(Π^{(t)}_{≤i}) ≤ 2^i γ_l^{i+1}. Its bound is in terms of γ_l, while γ_c is the congestion parameter. So the cited claim gives γ_l^{O(L)}, not γ_c^{O(L)}. Lemma 5.9 states its bound as (γ_cγ_l)^{O(L)}, so the stated result still holds. The symbol in this step does not match the claim it cites.

Second check: another model agreed

• p. 59 Algorithm 5, line 18

  m(γs/k)i+1/ log2 n then

• p. 59 Proof of Lemma 7.9, runtime

  However, the rebuild happens at most every m(γs/k)i0/ log2 n total updates to graphs at level i0.

Only the authors can say what is right here.

Judge's note: Both statements are on page 59. Because γs/k < 1, the algorithm's threshold is smaller than the one used in the amortization, so rebuilds can happen more often than the analysis assumes. Only the authors can say which threshold is intended (or how it relates to Lemma 7.8's m/(k log^2 n) limit). Whether the final m^{o(1)} bound is affected is not assessed.

Second check: another model agreed

• p. 70

  Any such counter is reset during a WIN at some level i < j.

Judge's note: Page 70 image: the outline paragraph says i ≤ j, and the displayed sum Σ_{j=i}^d includes j = i. Page 65 Line 8 resets fix_j for j ≥ i. The strict inequality is inconsistent with these.

Second check: another model agreed

• p. 78 Text after Lemma 10.8

  until 1⊤y ≤F ∗+ 50νm/t. Once this holds, we will double the value of t

• p. 81 Proof of Theorem 10.13

  whether 1⊤y(f) −F ∗≤20m/t. If so, we double t

• p. 78 Section 10.1, before the gradient/length definitions

  until 1⊤y ≤F ∗+ 50νm/t

• p. 81 Proof of Theorem 10.13

  check whether 1⊤y(f) −F ∗≤20m/t

Only the authors can say what is right here.

Judge's note: Both thresholds appear as quoted on the PDF pp.78 and 81 images. Lemma 10.10 assumes a gap of at least 10m/t, and the potential-increase argument 'Z2t(f) ≤ 20m + Zt(f)' uses 20m/t. The paper does not reconcile the 50νm/t of the overview with the 20m/t of the formal proof, and ν ≥ 1. Both thresholds are O(m/t) for constant ν, so this is a consistency question for the authors.

Second check: another model agreed

• p. 82 Proof of Theorem 10.13

  w def = 50+∥ℓ(f)◦c∥1

Judge's note: Checked on the PDF p.82 image. Lemma 9.2 (text line 5779) defines w(t) = 50 + |ℓ(t) ◦ c(t)| and checks the coordinate-wise width condition of Definition 6.1. The proof of Theorem 10.13 claims 'an identical analysis to Lemma 9.2' but prints an ℓ1 norm. The evident intent is the entrywise absolute value.

Second check: another model agreed

• p. 96 Proof of Lemma 4.12, bound on Φ(f^(init))

  e are all half-integral.

Only the authors can say what is right here.

Judge's note: Lemma 4.12 and eq. (8) allow integral u^-, u^+ in {−U,…,U} with u^- ≤ u^+; I found no statement requiring strict inequality. The potential (9) contains (u_e^+ − f_e)^{-α} + (f_e − u_e^-)^{-α}. My counterexample: if u_e^- = u_e^+ = 3, then f_e = 3 and both residuals are 0. Zero is half-integral, so the step 'half-integral ⇒ ≥ 1/2' fails, the terms are 0^{-α} = ∞, and Φ(f^(init)) ≤ 200m log mU fails for the construction as printed. The lemma is an existence claim, and fixing such edges by moving their flow into the demands restores it, so I treat this as a proof step that needs fixing (S3), not a false result.

Second check: another model agreed

• p. 102 Appendix B.4

  bound f stri e ≤kW = 0.1t

• p. 101 Appendix B.4

  Let t = 10kW log2 n = eO(k).

• p. 101 Proof of Lemma 6.6

  f stre ≤kW log2 n. Let t = 10kW log2 n

• p. 102 MWU bound

  f stri e ≤kW = 0.1t

Only the authors can say what is right here.

Judge's note: Page images p101 and p102 match the quotes. My reworking: 0.1·t = 0.1·10kW log^2 n = kW log^2 n, which is not kW. The bound actually available is str̃ ≤ kW log^2 n = 0.1t. That still gives str̃/t ≤ 0.1, which is what the step e^x ≤ 1+2x needs, so Lemma 6.6 is unaffected. A log^2 n factor appears to have been dropped.

Second check: another model agreed

• p. 105 Lemma C.9

  and capacities u ∈{−U, . . . , U}, computes an optimal

• p. 105 Lemma C.9 statement

  capacities u ∈{−U, . . . , U}

• p. 102 definition of (58)

  capacity u ∈{1, . . . , U}E

• p. 103 Definition of TMCC

  capacities u ∈{1, . . . , U}E

Judge's note: p102 (page 99) defines (58) with u ∈ {1,…,U}^E. p105 (page 102) shows Lemma C.9 with {−U,…,U} and no edge index. This looks like a notation slip with an evident fix ({1,…,U}^E); negative capacities have no meaning in (58), where 0 ≤ f_e ≤ u_e.

Second check: another model agreed

• p. 106 Lemma C.10 statement

  O(TA(m) log m log U + m log m log U)-time

• p. 109 end of proof of Lemma C.10

  Overall, the runtime is O(TA(m) log m log mU + m log m log mU)

Only the authors can say what is right here.

Judge's note: p106 (page 103) shows the lemma with log U and the clause with log mU. p109 (page 106) shows Algorithm 10 with T ← O(log U) and the proof deriving O(log mU) iterations. The two forms agree only when log m = O(log U); the authors should say which is intended.

Second check: another model agreed

• p. 107 Lemma C.14 statement

  f B is an integral 1.1-approximate solution

• p. 109 proof of Lemma C.10

  Lemma C.14 states that the augmenting circulation ∆f is always a 2-approximation

• p. 107 Lemma C.14 statement

  is an integral 1.1-approximate solution for the original

• p. 107

  f B is an integral 1.1-approximate solution for the original

Judge's note: Checked p.107 and p.109. A 1.1-approximation is also a 2-approximation, so the argument is valid. Only the wording 'states ... 2-approximation' misquotes the lemma. Its proof actually gives a (1−2m^−8) factor.

Second check: another model agreed

• p. 109 Algorithm 10, line 3

  T ←O(log U)

• p. 109 Proof of Lemma C.10

  After T = O(log m + log U) = O(log mU) iterations

Judge's note: Checked p.109 and the statement of Lemma C.10 in the text layer (runtime 'O(T_A(m) log m log U + ...)', and 'log m log mU' in the next sentence). The proof needs m^11·U/2^T ≤ 1/2, i.e. T ≥ log2(2m^11·U). When U is small relative to m, O(log U) iterations do not meet this. The algorithm line and part of the lemma statement should read O(log mU).

Second check: another model agreed

• p. 110 Appendix D

  runs in near-linear time to compute p-norm flows

Judge's note: Checked p.110. Theorem 10.14 in the text layer states 'in m^{1+o(1)} time'. The paper uses 'almost-linear' for m^{1+o(1)} and uses 'nearly-linear' for Õ(m) results (e.g. [ST04]), so this wording is inconsistent.

Second check: another model agreed

• p. 111 Appendix D, Negative Shortest-Paths

  ds = n and dv = −1 for all v ∈V

Judge's note: Checked p.111. Flow demands must sum to zero. Example with n = 10: 10 − 9 = 1 ≠ 0. This is an informal sketch with an evident fix.

Second check: another model agreed

• p. 9 Section 2.1, text after Eq. (2)

  for demands d ∈RE, lower and upper capacities

• p. 4 Section 1, problem definition

  vertex demands d ∈RV

• p. 9 Section 2.1, below eq. (2)

  for demands d ∈RE

Judge's note: The page image of p.9 shows R^E for d. Section 1 (p.4) and Section 3 ('routes a demand d ∈ R^V') define demands on vertices. The intended meaning is clear from context, so this is a notation slip.

Second check: none (judge only)

• p. 94 Appendix A.1

  O(m min(√m, n2/3 log U) for max-flow

• p. 94 Appendix A.1

  O(m min(√m, n2/3 log U) for

• p. 4 Introduction

  eO(m min{m1/2, n2/3} log U)

Judge's note: The p94 crop shows the unbalanced parentheses. The introduction (text near line 237, p4) puts log U outside the min. Because of the missing parenthesis, the appendix leaves unclear whether log U multiplies the whole bound. The fix is evident: close the min before log U.

Second check: none (judge only)

• p. 6 Section 1.2

  required in the the recent works on robust interior point methods

• p. 6 Section 1.2

  required in the the recent works

• p. 6

  than those required in the the recent works on robust interior point methods

• p. 6

  actors than those required in the the recent works on rob

Judge's note: The page image of p.6 shows 'the the'.

Second check: code check

• p. 7 Informal Theorem 1.6

  the set of edges that are embed into a fixed edge e ∈H

• p. 7 Informal Theorem 1.6

  the set of edges that are embed into a fixed edge

• p. 7 after Informal Thm 1.5

  are utilized to efficiently implementing the ℓ1 IPM algorithm

Judge's note: Both slips are visible on the page image of p.7.

Second check: none (judge only)

• p. 9 Section 2.1

  able to argue that a solving sequence of

• p. 9 Sec 2.1

  able to argue that a solving sequence of eO(m) ℓ1 minimizing subproblems

Judge's note: Visible on the page image of p.9.

Second check: none (judge only)

• p. 14 Section 2.3

  forcing both its endpoints to become root notes

• p. 14 Forest Routings paragraph

  both its endpoints to become root notes

Judge's note: Visible on the page image of p.14. The previous sentence uses 'root nodes'.

Second check: none (judge only)

• p. 20 Section 2.7, item 3

  we maintain the spannner

• p. 20 Sec 2.7 item 3

  we maintain the spannner such that

• p. 20

  we maintain the spannner such that for every edge

Judge's note: The crop shows "spannner" with three n's.

Second check: none (judge only)

• p. 20 Sec 2.6 last paragraph

  a data structure that handles successfully finds update cycles

• p. 20

  data structure that handles successfully finds

Judge's note: The crop shows the sentence as quoted. It has two verbs, so one of them ("handles") should go.

Second check: none (judge only)

• p. 21 Section 2.7, A Static Algorithm

  is the set of edges in Hi with endpoints in X and S

• p. 21 Section 2.7, A Static Algorithm

  with endpoints in X and S

• p. 21

  with endpoints in X and S and volHi(Y )

Judge's note: The crop shows "X and S̄" (S with an overbar). The cut has just been defined as (X, X̄) with X̄ = V(H_i) \ X, and S is not defined at this point. The symbol is a slip.

Second check: none (judge only)

• p. 22 Section 2.7, Dynamic Algorithm

  the maximum length of the the embedding paths

• p. 22

  edges), the maximum length of the the embedding paths has

Judge's note: The crop shows "the the".

Second check: code check

• p. 24 Section 3, Graphs

  and ∆min(G) denote the maximum and minimum degree of graph H.

• p. 24 Graphs paragraph

  the maximum and minimum degree of graph H

• p. 24 Section 3, Graphs

  minimum degree of graph H

• p. 24

  denote the maximum and minimum degree of graph H

Judge's note: The crop and p.24 show the sentence as quoted. The notation is defined for G.

Second check: none (judge only)

• p. 25 Section 3, Graph Embeddings

  is an graph-embedding from G into H

• p. 25 Section 3, Dynamic Graphs

  Enc(u) of an update u ∈U(t) be the size of the encoding

Judge's note: The full-page image of PDF p.25 (printed page 22) shows both as quoted.

Second check: none (judge only)

• p. 26 Lemma 3.3, item 4

  or or query the value fe

• p. 26 Lemma 3.3 item 4

  or or query the value fe in amortized time

Judge's note: The crop shows "or or".

Second check: none (judge only)

• p. 31 Lemma 4.7 statement

  Let eg ∈RE satisfy L(g)−1 (eg −g(f))

• p. 31 Lemma 4.7 hypothesis

  L(g)−1 (eg −g(f))

• p. 31 proof

  g(f)⊤(f ∗−g)

Judge's note: Page image p031 shows L(g)^{-1} in the statement of Lemma 4.7. L = diag(ℓ(f)) is a function of the flow; Lemma 4.4, Lemma 4.8 and the proof of 4.7 itself all use L(f)^{-1}. The (f*−g) typo, which some notes in this cluster also raise, is judged in C037.

Second check: none (judge only)

• p. 31 Proof of Lemma 4.7

  eg⊤(f ∗−f) = g(f)⊤(f ∗−g) + (eg −g(f))⊤(f ∗−f)

• p. 31 Proof of Lemma 4.7, line starting g̃ᵀ(f*−f) =

  g(f)⊤(f ∗−g) + (eg −g(f))⊤(f ∗−f)

Judge's note: Page image p031 shows (f*−g). The decomposition only holds with f*−f in both terms, and g is a gradient, not a flow.

Second check: none (judge only)

• p. 31 Proof of Lemma 4.7, (ii)

  follows from the the conditions on

• p. 31

  ∞norms, and (ii) follows from the the conditions on eg. T

Judge's note: The doubled word is visible on page image p031.

Second check: code check

• p. 34 Lemma 4.12 statement

  capacities c, u−, u+ ∈{−U, . . . , U}V

• p. 34 Lemma 4.12

  c, u−, u+ ∈{−U, . . . , U}V

Judge's note: Page image p034. Costs and capacities are edge vectors, and the output instance in the same lemma is typed correctly as {…}^{E(G̃)}. Only the demands d are indexed by V.

Second check: none (judge only)

• p. 34 Theorem 5.1, item 3

  we have P t′≤t |D(t′)| = eO P t′≤t |U(t)| · n1/L(γcγl)O(L)

Judge's note: Page image p034 shows U^{(t)} inside a sum over t′. Item 1 of the same theorem writes |U^{(t′)}|.

Second check: none (judge only)

• p. 40 Sec 5.2

  Recall the definiton of expanders.

Judge's note: Seen on the p.40 page image, just above Definition 5.10.

Second check: none (judge only)

• p. 41 Algorithm 2, line 9

  while there exists an edge e ∈E(J[Xi]) with

Judge's note: p.41 image: lines 5, 6 and the comment use J_i[X], and the proof of Claim 5.15 (p.43) uses E(J_i[X]). X_i is never defined, so the index is misplaced.

Second check: none (judge only)

• p. 43 Claim 5.16

  with probability at least 1 −n−2c.

• p. 43 Claim 5.16

  with probability at least 1 −n−2c

• p. 43 Claim 5.16

  with probability at least

Judge's note: p.43 image: the claim prints n^{-2c}, but its own proof gives 1−2n^{-4C}. Theorem 5.5 uses n^{-C}, and no lowercase constant c is defined for this purpose.

Second check: none (judge only)

• p. 43 Proof of Claim 5.15

  loop starting in Line 9 by by O(log(m))

• p. 43 Proof of Claim 5.15

  that where not embedded before

• p. 43 Proof of Claim 5.15

  starting in Line 9 by by O(log(m))

• p. 43

  while loop starting in Line 9 by by O(log(m)). We can t

Judge's note: Seen on the p.43 page image. The 'where'/'were' typo in the same proof is handled under C052.

Second check: code check

• p. 43 Proof of Claim 5.15

  that where not embedded before the current while-loop iteration

• p. 43 same proof

  as the algorithm track congestion

Judge's note: Both are seen on the p.43 page image.

Second check: none (judge only)

• p. 46 Lemma 6.5, item 1

  q def = Pτ t=1 Enc(U(i))

Judge's note: p.46 image confirms the sum over t=1..τ with summand Enc(U^{(i)}). The summand should be U^{(t)}.

Second check: none (judge only)

• p. 49 end of Sec 6.4

  we gives a data structure whose guarantee is weaker

• p. 61 before Lemma 7.13

  indeed given the correct total gradient

Judge's note: Both phrases are seen on the p.49 page image and the p.61 crop.

Second check: none (judge only)

• p. 50 Def 7.3

  with a tree T, arooted spanning forest

Judge's note: The p.50 page image shows 'arooted' with no space, so this is not an extraction artefact.

Second check: none (judge only)

• p. 52 Proof of Lemma 7.5, expectation display

  t X i=j λj f strj e

• p. 52 Proof of Lemma 7.5, end

  we get that there exists an i∗satisfying (26)

• p. 51 Lemma 7.5 item 2

  there is an j∗∈[B] only depending on w(0)

• p. 52 end of proof

  there exists an i∗satisfying

Judge's note: I checked the p.52 image (expectation display and last paragraph) and the p.51 image (Lemma 7.5 Item 2, which uses j* and F_{j*} in (26)). The sum should run over i=1..t with λ_i and the i-th tree's stretch. The witness index is renamed from j* to i*. Both are index typos.

Second check: none (judge only)

• p. 59 Algorithm 5 caption

  rebuilds the data structure of level at least ds at stage t0

Judge's note: Page 59 image: lines 8–9 of the algorithm show Rebuild(i0,t0) looping over i = i0,…,d−1. 'd_s' is not defined in this context; it should be i0.

Second check: none (judge only)

• p. 59 Proof of Lemma 7.9

  induction on t and the the level i

• p. 59

  ow (32) by induction on t and the the level i, and prove

Judge's note: Visible on the page 59 image, bottom paragraph.

Second check: code check

• p. 64 Proof of Theorem 7.1

  γs = γr = exp(log3/4 log log m)

• p. 64

  e choice γs = γr = exp(log3/4 log log m), d = log1/8 m an

Judge's note: Page 64 image confirms the printed formula has no 'm' after log^{3/4}. Lemma 7.8 (p.54) gives exp(O(log^{3/4} m log log m)). The repeated 'log' itself is the legitimate iterated logarithm.

Second check: code check

• p. 64 Section 8 intro

  When is this does not happen

• p. 64 Definition 8.1

  ad- vesary

• p. 64 Def 8.1

  played between a player and an ad- vesary

• p. 64 Rebuilding game parameters

  integers parameters size m > 0

Judge's note: All four phrases are visible on the page 64 image.

Second check: none (judge only)

• p. 66 Section 8, rebuilding game algorithm

  thus rebuiling levels j ≥i

• p. 66 Section 8.1

  outline the main the main elements

Judge's note: All three are visible on the page 66 image.

Second check: none (judge only)

• p. 71 Proof of Lemma 8.3

  amortized to toward a round across all levels is .

• p. 66 Sec 8 algorithm description

  (thus rebuiling levels j ≥i)

• p. 66 same

  a fixing step occured

• p. 67 after Lemma 8.5

  This lemma tells use that

Judge's note: Every quoted slip is visible in the page images and crops: rebuiling→rebuilding, occured→occurred, use→us, form→from, missing 'at', and 'amortized to toward … is .', which is garbled and ends in a dangling period before eq. (43).

Second check: none (judge only)

• p. 77 Lemma 10.7

  Let f : X →R be a convex function on an open set X ⊆R2.

• p. 77 Eq. (48)

  ζ′(x) = ⟨∇ψ(x, y(x)), v⟩= fx(x, y(x)),

• p. 78 before (52)

  Each phase will requires approximately

• p. 81 before Lemma 10.12

  a good quality circlation ∆

Judge's note: Checked on the page images of PDF pp.77, 78 and 81. The function is introduced as f, but the definitions of y(x) and ζ(x) and equations (49)–(51) use ψ. Equation (48) and its proof write f_x and f_y, and the proof of (51) says 'recall that f_y(x,y(x))=0' and then uses ψ_xy and ψ_yy. Bold f is also the paper's symbol for flows. The intended meaning is clear, so these are notation slips and copy-editing errors. 'requires' should be 'require' and 'circlation' should be 'circulation'.

Second check: none (judge only)

• p. 83 Section 10.2

  add a few vertex v∗to the graph G

• p. 83 Section 10.2

  force f to to have 0 demand

• p. 83 same paragraph

  (eg. using a logarithmic barrier)

• p. 83

  ic barrier). Finally, force f to to have 0 demand on th

Judge's note: Checked on the PDF p.83 image. All three typos appear as quoted. Only a single vertex v∗ is added, so 'a few' should be 'a new'.

Second check: code check

• p. 89 Reference [HK73]

  “An $nˆ{5/2} $ Algorithm for Max- imum Matchings in Bipartite Graphs”

• p. 86 [BLSS20]

  Proccedings of the 52nd Annual

• p. 89 [HK73]

  An $nˆ{5/2} $ Algorithm for Max-

• p. 86

  In: Proccedings of the 52nd Annual

Judge's note: The p89 crop shows the dollar signs and braces printed literally in the [HK73] title. The p86 crop shows 'Proccedings' in italics in [BLSS20]. Both are visible on the page, so neither is an extraction artefact.

Second check: none (judge only)

• p. 93 App A

  can be found the CACM article

Judge's note: The p93 crop shows the sentence exactly as quoted. The other typos this reviewer lists on p95 are handled under C111.

Second check: none (judge only)

• p. 95 Appendix A.1, second bullet

  [CKMST11; Mąd13; LS19; Mąd16; LS19; KLS20]

Judge's note: The full page image p95 (printed page 92) shows LS19 twice in the same bracket. One occurrence may have been meant as a different reference; only the authors can say.

Second check: none (judge only)

• p. 95 Appendix A

  data structured tailored to electrical

• p. 95 Appendix A.2

  arbitrary integer capcities

• p. 95 Appendix A.1

  via data structured tailored to electrical

• p. 95 A.2

  Many these algorithms

Judge's note: Each typo is visible in the page images: p95 (data structured, capcities, Many these), p110 (the the, can simple split, insert and edge), p111 (miminizing) and p112 (find project). All are cosmetic.

Second check: none (judge only)

• p. 98 Proof of Lemma 6.5 (heavy-light)

  roots that an edge e is assigned too

• p. 102 Proof of Lemma 6.6

  v1 def = 1 is an the all 1’s vector

• p. 102 same

  Next, we upper bounds ∥vi∥1

Judge's note: Seen in the crops from p98 and p102.

Second check: none (judge only)

• p. 110 Appendix D, Extensions of Theorem 1.1

  for each vertex v ∈V where bv ≤0 (resp. bv > 0), with lower capacity 0, upper capacity |bv|

• p. 110 Appendix D, Extensions of Theorem 1.1

  for each vertex v ∈V where bv ≤0 (resp. bv > 0)

• p. 110 App D, Extensions

  where bv ≤0 (resp. bv > 0)

Judge's note: Checked p.110. d is defined in the preceding sentence, and b_v appears with no definition. Later on the same page, b denotes the worker-assignment degree vector, a different object. d_v is evidently what was meant.

Second check: none (judge only)

• p. 110 Appendix D, Bipartite Matching

  the the worker assignment problem

• p. 110

  Our result implies that the the worker assignment problem

• p. 110

  ists. Our result implies that the the worker assignment p

Judge's note: Visible on p.110 (printed p.107).

Second check: code check

• p. 110 Appendix D, Extensions of Theorem 1.1

  then insert and edge (vin, vout)

• p. 110 Extensions of Theorem 1.1

  one can simple split

• p. 110 same

  insert and edge (vin, vout)

• p. 110

  then insert and edge (vin, vout) with

Judge's note: Both are visible on p.110.

Second check: none (judge only)

• p. 111 Appendix D

  using Cut-Link Trees [ST83] on can recover a negative cycle

• p. 111 Appendix D

  using Cut-Link Trees [ST83] on can recover

• p. 111 Appendix D, negative cycle detection

  using Cut-Link Trees [ST83]

• p. 111 Appendix D, Negative Shortest-Paths

  Cut-Link Trees [ST83]

Judge's note: Checked p.111. Everywhere else the paper calls the [ST83] structure 'link-cut trees' (text layer lines 214, 709, 3216). 'on' is a typo for 'one'.

Second check: none (judge only)

• p. 111 Appendix D, Connectivity

  obtained by miminizing over

• p. 112 Isotonic regression

  The goal is to find project y on to the space

Judge's note: Checked p.111. The 'find project y' part of this cluster is handled separately as C135.

Second check: none (judge only)

• p. 112 Appendix D, Isotonic Regression

  The goal is to find project y

Judge's note: Visible on p.112 (printed p.109).

Second check: none (judge only)