{"id":"4f05a354-27f0-4fd8-a145-f752cfb11246","arxiv_id":"2501.10632","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"By rounding tiny multiplicative weights to zero, the authors localize Sherman's flow algorithm and obtain a (1+epsilon)-approximate k-commodity flow algorithm on expanders in (m + epsilon^{-3}k^3D) n^{o(1)} time.","lead":"Routing many commodities through a network usually costs time proportional to the number of commodities times the network size. This paper gives a way to route them approximately on well-connected networks in time that mostly depends on the total demand instead.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1.2's expander application is built on Theorem 3.1, stated only as 'implicit in [CHS24]' and neither proved nor located; if that theorem's assumptions or constants differ, the high-accuracy expander claim does not follow.","rationale":"I focused on the expander application because the local-algorithm half of the paper (Theorems 2.1 and 2.9) is developed with self-contained proofs; the charging arguments in Lemmas 2.6-2.8 and 2.13-2.15 are the core of the local runtime and appear internally consistent on careful read. The expander theorem, however, is assembled from Theorem 2.9 plus Theorem 3.1, and Theorem 3.1 is load-bearing: it alone converts small per-vertex residual demand into a global (1+eps)-congestion flow at the claimed speed. The manuscript gives no proof and no pointer to a theorem statement in [CHS24], so the correctness of Theorem 1.2 cannot be checked from this paper alone. A second, smaller issue is the final runtime chain: after substituting eps~ = eps/(kP), the term eps^{-2} k^3 is dropped, and the displayed equality to (m + eps^{-3} k^3 D) is only valid when that term is dominated (roughly when D is not much smaller than eps/P, with the outer poly factor absorbing constants); otherwise the theorem needs a separate small-demand case. This is a statement-level repair, not a conceptual one, and the reader already flagged it. My read does not change the reader's CONDITIONAL verdict: the local-algorithm contribution is well supported, but the expander theorem should be verified against [CHS24] or reproved before unconditional acceptance.","tokens_in":17625,"tokens_out":34750,"duration_ms":378057,"concrete_test":"Locate in [CHS24] (arXiv:2405.03908) the exact theorem matching Theorem 3.1: an arbitrary number of weighted source-sink pairs, per-vertex incident demand at most alpha deg(v), deterministic, time (m + ell) poly(1/phi) 2^{O(sqrt(log n log log n))}, and congestion alpha poly(1/phi) 2^{O(sqrt(log n log log n))} with no hidden restriction on alpha or on the demand values. If no such statement exists, or if the stated constants/assumptions differ, Theorem 1.2 needs a proof or a precise reference; if the matching theorem exists, cite it explicitly and the primary concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's headline expander result, Theorem 1.2, is assembled in Section 3 from the local algorithm (Theorem 2.9) plus Theorem 3.1. Theorem 3.1 is introduced with the sentence 'The following is implicit in [CHS24]' and is not proved or pinpointed to a specific theorem in that reference. This is not a cosmetic gap: Theorem 3.1 is the mechanism that converts the local algorithm's per-vertex residual demands |r_j(v)| <= eps~ deg(v) into an exact (1+eps)-congestion flow, and it supplies both the correctness and the poly(1/phi) 2^{O(sqrt(log n log log n))} factors in the final runtime. If [CHS24]'s actual routing guarantee has different parameters -- for example, if alpha must be a fixed constant rather than arbitrarily small, if it handles only unit demands, if its congestion or time has a hidden dependence on total demand, or if its poly(1/phi) exponent is incompatible -- then Theorem 1.2 does not follow as stated. Because the entire barrier-breaking expander application rests on this unstated external dependency, it is the most load-bearing soft spot in the paper.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a local algorithm for multi-commodity flow on unit-capacity undirected graphs. The algorithm runs T = O(eps^-2 log n) rounds of multiplicative weights over vertex-commodity pairs; in each round it rounds all weights below n to zero, sends maximum-capacity flow along edges according to the resulting rounded potentials, and updates the weights from the per-vertex excesses. The main theorem, Theorem 2.9, states that in O(eps^-2 log n(||b||_0 + eps^-1 ||b||_1)) time the algorithm either produces a certificate that the k-commodity demand is infeasible or produces a feasible k-commodity flow whose residual demand at every vertex v and commodity j is at most eps deg(v). The paper then applies this to phi-expanders: by routing the residual demands with an expander-routing routine stated as 'implicit in [CHS24]' (Theorem 3.1), it claims a deterministic (1+eps)-approximation algorithm for k-commodity flow in (m + eps^-3 k^3 D) poly(1/phi) 2^{O(sqrt(log n log log n))} time, thereby breaking the km barrier on expanders.","tokens_in":17787,"tokens_out":14807,"duration_ms":155849,"significance":"The local-algorithm portion is an interesting and, on my reading, sound contribution. The charging argument in Lemmas 2.7 and 2.14 is careful, the approximate-MWU theorem (Theorem 2.3) is used correctly, and the infeasibility certificates are meaningful. I found no internal circularity in the MWU analysis: the guarantees are derived from the algorithm's own update rules rather than assumed. The rounding idea for multiplicative weights may well be reusable. If the expander application were fully justified, Theorem 1.2 would be a significant barrier result. However, the headline expander theorem currently rests on an unverified external theorem and on a runtime derivation that drops a non-negligible term, so the significance of the expander claim is conditional as written.","major_comments":[{"comment":"The entire expander application depends on Theorem 3.1, which is introduced with the sentence 'The following is implicit in [CHS24]' and is then used without a proof or a precise pointer to a theorem in that reference. This is load-bearing: Theorem 3.1 is the mechanism that turns the residual guarantees of Theorem 2.9 into a (1+eps)-congestion flow, and it supplies the poly(1/phi) 2^{O(sqrt(log n log log n))} factors in both the correctness and the running time of Theorem 1.2. As written, the reader cannot check whether the hypotheses and constants of the cited result match the needed statement (deterministic, arbitrary positive alpha, weighted demands, congestion alpha poly(1/phi) 2^{O(...)}, and time (m+ell) poly(1/phi) 2^{O(...)}). The proof of Theorem 1.2 should either include a proof of Theorem 3.1 or restate the exact theorem from [CHS24] and verify that it implies the stated form; otherwise Theorem 1.2 remains conditional on an unverified external claim.","section":"Section 3, Theorem 3.1"},{"comment":"The displayed derivation at the end of Section 3 contains the step (m + tilde-eps^-2 k + tilde-eps^-3 D) = (m + eps^-2 k^3 + eps^-3 k^3 D) = (m + eps^-3 k^3 D). The middle expression contains the term eps^-2 k^3, which is dropped without justification. This term is dominated by eps^-3 k^3 D only when D >= eps, and no such assumption appears in Theorem 1.2; it is also not necessarily dominated by m for the stated parameter range. Consequently, the claimed runtime in Theorem 1.2 is strictly smaller than the runtime established by the proof. The theorem should state the bound with the additional eps^-2 k^3 term, or the missing dominance assumption should be stated and justified.","section":"Section 3, proof of Theorem 1.2"}],"minor_comments":[{"comment":"The definition of V_<x should be {v : tilde-phi^i_v < x}; the text as printed uses '>' in both definitions.","section":"Lemma 2.2"},{"comment":"The assumption is written as b_j(v) <= deg(v), but the proof and the sentence before the lemma require |b_j(v)| <= deg(v). The certificate returned when this check fails should also be specified; a single-commodity cut {v} with |b_j(v)| > deg(v) suffices.","section":"Lemma 2.11"},{"comment":"The parameter nu is declared in the statement of Theorem 2.3 but is never used; either remove it or indicate its intended role.","section":"Theorem 2.3"},{"comment":"After decomposing r_j into weighted pairs, the expression sum_{i in [ell_j]} d_{j,ell_j} should be sum_{i in [ell_j]} d_{j,i}.","section":"Section 3, residual decomposition"},{"comment":"The reduction says a greedy decomposition achieves ell_j <= ||r_j||_0, but it should also state explicitly that the decomposition can be chosen so that the total incident demand at each vertex v is |r_j(v)|; this is what justifies the parameter alpha = k tilde-eps in the call to Theorem 3.1.","section":"Section 3, call to Theorem 3.1"}],"recommendation":"major_revision","confidential_remarks":"The local-algorithm contribution appears sound and is likely publishable. The main risk is whether [CHS24] indeed contains Theorem 3.1 with the required parameters; the authors should be asked to pin that down precisely and to correct the stated runtime of Theorem 1.2. I do not see a reason to reject at this stage."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Jason and Saranurak have a genuinely new result: the first local algorithm for multi-commodity flow, built on a clean observation that Sherman's MWU oracle can be run on rounded weights. The single- and multi-commodity proofs in Section 2 are careful, and the approximate-weights MWU theorem (2.3) is a real analytic contribution, not a restatement. The charging argument in Lemma 2.7 and its multi-commodity analogue are sound; I checked the edge-by-edge potential argument and it goes through. The infeasibility certificate for multi-commodity flow via the LP dual in Lemma 2.10 is also correct. So the core of the paper is in good shape.\n\nThe soft spots are real but manageable. The expander application, Theorem 1.2, depends entirely on Theorem 3.1, which is stated as 'implicit in [CHS24]' with no proof and no pointer to a specific lemma. That is not a cosmetic gap; Theorem 3.1 supplies both correctness and the poly(1/phi) 2^O(sqrt(log n log log n)) factors in the final runtime. The stated parameters--arbitrarily small alpha, weighted pairs, deterministic time (m+ell) poly--need to be verified against [CHS24]. This is likely a writing issue rather than a mathematical one, but it must be fixed before the paper is accepted.\n\nSecond, the runtime derivation in Section 3 drops the epsilon^{-2}k^3 term. After substituting tilde epsilon, the algorithm actually runs in time (m + epsilon^{-2} k^3 + epsilon^{-3} k^3 D) * poly, and the last line keeps only the epsilon^{-3} term. That is only dominated when D >= epsilon; for tiny total demand the stated bound is smaller than what is proven. The theorem should be restated with both terms, or the case D < epsilon handled separately. Minor but it makes Theorem 1.2 technically false as stated.\n\nThere are also typos in Lemma 2.2's definition of V_{<x} and in the integral identity; these are cosmetic.\n\nOverall: the local algorithm is a real advance and deserves a serious referee. The expander application is likely correct but needs the CHS24 dependency made explicit and the runtime bound fixed. I'd send it to review; the fixes are relatively small and the core contribution stands.","headline":"The local multi-commodity flow algorithm is the real contribution; the expander application is a plausible but currently under-supported add-on, fixable with a pointer to CHS24 and a corrected runtime bound.","tokens_in":18429,"tokens_out":4174,"would_cite":true,"duration_ms":38367,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q25","68W40","05C85","90C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper gives the first local algorithm for multi-commodity flow, and on expander graphs it computes a (1+ε)-approximate flow in time that avoids the km barrier.","keywords":["multi-commodity flow","local algorithms","expander graphs","multiplicative weights update","Sherman's algorithm","sublinear time","flow congestion","infeasibility certificate"],"falsifier":"The central claim would be refuted by any unit-capacity graph, $k$-commodity source function, and $\\varepsilon$ for which the output flow leaves a vertex with residual demand exceeding $\\varepsilon\\deg(v)$, or for which the algorithm's runtime violates $O(\\varepsilon^{-2}\\log n(\\|b\\|_0+\\varepsilon^{-1}\\|b\\|_1))$; a small path or cycle instance can be checked by simulating the stated update rule. The expander theorem would be refuted by exhibiting a $\\varphi$-expander and a residual demand of the form Theorem 2.9 leaves behind that the cited expander-routing routine cannot route with congestion $\\varepsilon$ in the claimed time.","tokens_in":17316,"feed_emoji":"🌐","tokens_out":9684,"duration_ms":86529,"temperature":0.7,"pith_summary":"This paper claims to remove a long-standing bottleneck in multi-commodity flow: finding a (1+ε)-approximate routing of k commodities on an undirected graph used to require time proportional to k times the number of edges, because even writing down the answer could be that large. The authors give the first local algorithm for the problem: it reads only a sparse demand and runs in time depending on the demand size, not the whole graph. On expander graphs, the same technique yields a (1+ε)-approximate flow in about m plus a demand-dependent term, breaking the Ω(km) barrier for high-accuracy flow for the first time. The mechanism is to run Sherman's algorithm inside a multiplicative-weights loop while rounding every tiny weight to zero, so that each iteration touches only vertices with large cumulative imbalance.","feed_headline":"On expanders, multicommodity flow finally beats the km time wall","feed_subtitle":"The new method routes k commodities on expander graphs in m plus demand-dependent time, without reading the whole graph.","key_machinery":"The engine is a localized version of Sherman's flow algorithm inside a Multiplicative Weights Update (MWU) loop. Each vertex maintains two nonnegative multiplicative weights, one for positive and one for negative potential, and each iteration routes unit flow along edges from higher to lower rounded potential. The rounding step zeroes every weight below $n$, so only vertices whose cumulative excess or deficit is at least $(\\ln n)/\\alpha$ keep nonzero potential and generate work; all other vertices behave as if their potential were zero, so no flow is sent between them. A refined MWU theorem (Theorem 2.3) shows that such additive approximation of the weights is harmless, while Lemma 2.7 charges the volume of active vertices to the input's $\\ell^1$ norm, yielding the runtime bound. The expander application then calls a separate deterministic expander-routing theorem (Theorem 3.1), cited as implicit in [CHS24], to route the leftover residual demand with only $\\varepsilon$ extra congestion.","core_discovery":"On a unit-capacity undirected graph $G=(V,E)$ with any $k$-commodity source function $b$, Theorem 2.9 gives an algorithm that, for error $\\varepsilon \\in (0,1)$, runs in $O(\\varepsilon^{-2}\\log n\\,(\\|b\\|_0+\\varepsilon^{-1}\\|b\\|_1))$ time and outputs either a certificate that the demand is infeasible or a feasible $k$-commodity flow whose residual demand at each vertex $v$ and commodity $j$ is at most $\\varepsilon\\deg(v)$. The application to expanders, Theorem 1.2, says that for a $\\varphi$-expander with total demand $D=\\sum_j d_j$, a flow of congestion $1+\\varepsilon$ (or an infeasibility certificate) is computed in $(m+\\varepsilon^{-3}k^3D)\\cdot\\mathrm{poly}(1/\\varphi)\\cdot 2^{O(\\sqrt{\\log n\\log\\log n})}$ time. The paper claims this is the first local multi-commodity flow algorithm and the first $(1+\\varepsilon)$-approximate multi-commodity flow algorithm on expanders that avoids the $\\Omega(km)$ time barrier.","pith_inferences":["A natural next step, not pursued here, is to use the same weight-rounding idea to localize other iterative graph algorithms whose update rules are driven by multiplicative weights.","The runtime's dependence on $\\|b\\|_1$ rather than the size of the whole graph suggests the algorithm may be especially useful in dynamic and distributed settings where demands change locally; the paper does not develop this application.","The expander theorem's stated rate $(m+\\varepsilon^{-3}k^3D)$ absorbs a separate $\\varepsilon^{-2}k^3$ term that is only dominated when the total demand $D$ is not too small, so comparisons for very small $D$ should use the full derived expression."],"forward_implications":["On any $\\varphi$-expander, a $(1+\\varepsilon)$-approximate $k$-commodity flow is computable in $(m+\\varepsilon^{-3}k^3D)\\cdot\\mathrm{poly}(1/\\varphi)\\cdot 2^{O(\\sqrt{\\log n\\log\\log n})}$ time, with no factor of $km$.","Sparse demands, measured by $\\|b\\|_0$ and $\\|b\\|_1$, can be almost fully routed in sublinear time without reading the whole graph, and infeasibility is certified when the demand cannot be routed at all.","The rounded-weight MWU analysis applies to any MWU-based oracle whose per-round work is concentrated on the largest weights, so the localization trick is not limited to this specific flow algorithm.","Because the algorithm is deterministic and acknowledged by the paper to be immediately parallelizable, the same guarantee carries to settings where deterministic and low-depth algorithms are required."],"supporting_citations":[{"why":"Supplies the base flow algorithm that the paper localizes.","marker":"[She13]"},{"why":"Provides the deterministic expander-routing theorem (Theorem 3.1) used to finish residual demands on expanders.","marker":"[CHS24]"},{"why":"Establishes the earlier $\\Omega(km)$-time baseline for undirected multicommodity flow that Theorem 1.2 aims to break.","marker":"[She17]"},{"why":"Gives the previous sparse implicit representation with only constant approximation, the strongest contrast for expander flow.","marker":"[HHL+24]"}],"fun_headline_variants":["Local flow on expanders breaks the km time wall","Sublinear-time flow for k commodities on expanders","First local multicommodity flow algorithm for expanders","Sherman's algorithm localized avoids the km barrier"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The expander result rests on the cited claim that any residual demand with per-vertex load at most $\\alpha\\deg(v)$ on a $\\varphi$-expander can be routed with congestion $\\alpha\\,\\mathrm{poly}(1/\\varphi)2^{O(\\sqrt{\\log n\\log\\log n})}$ in near-linear time; if that cited expander-routing theorem is wrong or has different constants, Theorem 1.2's congestion and runtime do not follow.","fun_headline_variants_meta":{"raw":{"variants":["Local flow on expanders breaks the km time wall","Sublinear-time flow for k commodities on expanders","First local multicommodity flow algorithm for expanders","Sherman's algorithm localized avoids the km barrier"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001221,"raw_usage":{"total_tokens":5044,"prompt_tokens":988,"completion_tokens":4056,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":604,"completion_tokens_details":{"reasoning_tokens":3993}},"tokens_in":604,"tokens_out":4056,"duration_ms":32413,"temperature":1.0,"reasoning_tokens":3993,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T19:03:41.084807+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"The central claim would be refuted by any unit-capacity graph, $k$-commodity source function, and $\\varepsilon$ for which the output flow leaves a vertex with residual demand exceeding $\\varepsilon\\deg(v)$, or for which the algorithm's runtime violates $O(\\varepsilon^{-2}\\log n(\\|b\\|_0+\\varepsilon^{-1}\\|b\\|_1))$; a small path or cycle instance can be checked by simulating the stated update rule. The expander theorem would be refuted by exhibiting a $\\varphi$-expander and a residual demand of the form Theorem 2.9 leaves behind that the cited expander-routing routine cannot route with congestion $\\varepsilon$ in the claimed time.","supporting_citations":[],"review_version":1}