{"id":"a0ca858b-c2af-40e5-bfb1-8ecd8e9511ad","arxiv_id":"2506.04524","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A new analysis of an existing local algorithm yields O(log lambda)-round LOCAL and O(sqrt(log lambda) log log lambda)-round sublinear-space MPC algorithms for (1+epsilon)-approximate allocation in graphs of arboricity lambda.","lead":"This paper gives a faster parallel algorithm for a resource-allocation problem on sparse bipartite graphs, running in O(sqrt(log lambda) log log lambda) rounds instead of the previous O(log n). The result matters because allocation generalizes matching and is used in online advertising and task assignment, and lower round counts help big-data platforms scale.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"MPC ball-size bound omits factor (4τ+1) from number of β-level groups, so the claimed n^α memory and O(√logλ·loglogλ) rounds are not established.","rationale":"After a careful read, the LOCAL analysis (Theorem 9) appears sound: the arboricity argument bounding |N(L2τ)| by O(λ|N'|) and the level-set decomposition are standard and internally consistent. The main theorem, however, depends on the MPC simulation fitting B rounds into each machine. The stated degree bound d omits the factor from the number of β-level groups, which is a concrete omission: Algorithm 2 samples from each of 4τ+1 groups per vertex per round, so the per-vertex degree is roughly (4τ+1) times the reported d. Since τ grows logarithmically with λ, this factor is not a constant and affects the ball-size bound d^B. The paper's eq. (4) chooses B from d^B ≤ min{λ,n^α}; without accounting for the group factor, the memory claim is unjustified. This matches the reader's weakest_assumption, so I agree with the CONDITIONAL verdict. The sampling lemma (Lemma 11) is plausible and likely fixable, but the degree bound is the load-bearing gap because it directly underpins the algorithm's resource guarantees.","tokens_in":23064,"tokens_out":14787,"duration_ms":125955,"concrete_test":"Recompute the degree bound as d' = (4τ+1)·20(1+ε)^{2B}·log^2 n·ε^{-5} with τ = log_{1+ε}(4λ/ε)+1, and check whether (d')^B ≤ min{λ,n^α} holds for the B defined in eq. (4) for representative parameters (e.g., ε=0.1, λ=10^6, n=10^9, α=0.5). If it fails, find the largest B satisfying the bound and compare to Θ(√log λ); if the largest valid B is o(√log λ), the claimed round complexity is not achievable with n^α local memory.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 5 states 'The total degree per vertex is at most d = 20(1+ε)^{2B}·log^2 n·ε^{-5}' and then requires d^B ≤ min{λ,n^α} to set B in eq. (4). However, Algorithm 2 samples t = (1+ε)^{2B}·ε^{-5}·log n edges from each of 4τ+1 groups L_x (x∈[-2τ,2τ]) for every round index r∈[0,B). Thus the actual per-vertex degree in H_r is (4τ+1)·t, with τ = log_{1+ε}(4λ/ε)+1 = Θ((1/ε)log λ). The missing factor (4τ+1) enters d^B through B log τ, which for B=Θ(√log λ) is Θ(√log λ·log log λ). This is not vanishingly small relative to the log λ budget; for moderate λ it can exceed the slack in eq. (4). The paper provides no argument that a constant-factor smaller B still yields B=Θ(√log λ), so the claimed ball-size and memory bounds are not proven.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the allocation problem (a special case of b-matching on bipartite graphs with capacities only on one side) in the Massively Parallel Computation (MPC) model. The main claim is a (1+epsilon)-approximate allocation algorithm that runs in O_epsilon(sqrt(log lambda) log log lambda) MPC rounds, uses n^alpha local memory per machine and O~(lambda n) total memory, and does not require knowledge of the arboricity lambda. The proof route is: (i) a new analysis of the LOCAL algorithm of Agrawal, Zadimoghaddam, and Mirrokni [AZM18], showing that O_epsilon(log lambda) rounds suffice for a (2+epsilon)-approximate fractional allocation on graphs of arboricity lambda; (ii) an MPC simulation of O_epsilon(sqrt(log lambda)) of those LOCAL rounds via a graph-sparsification/ball-copying scheme in the style of Ghaffari and Uitto [GU19]; and (iii) a black-box application of the Ghaffari, Grunau, and Mitrovic [GGM22] framework to boost the approximation to 1+epsilon.","tokens_in":23366,"tokens_out":20963,"duration_ms":194991,"significance":"If the main result holds, it would be a meaningful step beyond the long-standing O(sqrt(log n))-round barrier for approximate matching in the sublinear MPC regime, specialized to graphs of low arboricity, and it would extend this progress from matching to the more general allocation problem. The LOCAL analysis in Section 4 is coherent and elegant: the arboricity argument in Theorem 9 bounding the edges between N(L_{2tau}) and L_0 is checkable and appears sound. The paper also explicitly addresses the issue of not knowing lambda, which is a genuine practical concern in this line of work. The principal weaknesses are in the MPC simulation section (Section 5): the sampling estimator as written is not the correct estimator for the stratified sampling procedure, the per-vertex degree bound omits a factor from the number of beta-level groups, and the sample-count parameters are not matched to the concentration lemma. These issues are load-bearing for the claimed round, memory, and correctness guarantees, but they appear to be fixable within the scope of the paper, so the appropriate decision is major revision rather than rejection.","major_comments":[{"comment":"The estimator in line 5 is not compatible with the sampling process in line 3. Line 3 samples t edges uniformly at random from each level group L_x, so the resulting set N_{r,u} is a stratified sample whose sampling rate varies across groups; the ratio estimator |N_u|/|N_{r,u}| * sum_{v in N_{r,u}} beta_v is biased for beta_u = sum_{v in N_u} beta_v unless all groups have equal size. The correct estimator is sum_x (|L_x|/t) * sum_{v in sample_x} beta_v, with the appropriate min(t,|L_x|) adjustment when a group has fewer than t elements. As written, Lemma 12 does not follow from Lemma 11, and the equivalence argument in Appendix A.1 relies on Lemma 12. This is a central correctness issue for the MPC simulation.","section":"Section 5, Algorithm 2, lines 3 and 5; Lemma 12"},{"comment":"The per-vertex degree bound d omits the factor (4tau+1) coming from the number of beta-level groups. Algorithm 2 samples t edges from each of the 4tau+1 groups L_x (x in [-2tau,2tau]) for every round index r in [0,B), so the degree of a vertex in each H_r is at most (4tau+1)*t, not t. This missing factor enters the condition d^B <= min{lambda, n^alpha} through B log(4tau+1) = Theta(sqrt(log lambda) log log lambda), and the paper gives no argument that the constant in Eq. (4) can be reduced to absorb this term while preserving B = Theta(sqrt(log lambda)). Consequently, the claimed n^alpha local memory and O~(lambda n) total memory bounds are not established as written. This is fixable by choosing the constant in Eq. (4) sufficiently small, but the proof needs to be supplied.","section":"Section 5, paragraph defining d and Eq. (4)"},{"comment":"The sample count in Algorithm 2 is not matched to Lemma 11. Lemma 11 with ratio t_ratio = (1+epsilon)^B requires s >= 20(1+epsilon)^{2B} log n / epsilon^4 samples per group, whereas Algorithm 2 sets t = (1+epsilon)^{2B} epsilon^{-5} log n. The ratio t/s equals epsilon/20, so for constant epsilon (for example epsilon = 1/4) the algorithm samples strictly fewer elements than the concentration lemma requires. The text in Section 5 also claims a total degree d = 20(1+epsilon)^{2B} log^2 n epsilon^{-5}, which does not follow from the stated Lemma 11 bound. The parameters need to be corrected and the derivation of d needs to be made explicit before Lemma 12 can be considered proven.","section":"Section 5, Algorithm 2 parameters and Lemma 12"}],"minor_comments":[{"comment":"The pseudocode iterates over 'each vertex w in V(G)' but then writes 'E_{r,v,x} <- Sample t edges from N_v cap L_x', using an undefined variable v; this should be N_w or the loop variable should be v.","section":"Algorithm 2, line 3"},{"comment":"The symbol beta_u is used both for the true sum beta_u = sum_{v in N_u} beta_v and for the estimated quantity in Algorithm 2, line 5. Using a distinct notation such as hat(beta)_u for the estimate would improve readability and avoid confusion in Lemma 12.","section":"Section 5, notational overloading"},{"comment":"The proof labels 'Case 1' and 'Case 2' as if they were alternatives, but the bound in 'Case 1' is actually unconditional given the choice of s, and 'Case 2' proves a concentration event. Rewriting the proof as a single argument would make the logic clearer.","section":"Lemma 11, proof structure"},{"comment":"The text says 'we set B = B_epsilon/48' after Eq. (4), but Eq. (4) defines B_epsilon; please clarify the naming and the exact role of the factor 1/48 in the derivation of the ball-size bound.","section":"Eq. (4) and surrounding text"},{"comment":"The abstract claims 'no o(log n) round algorithm for constant-approximate allocation was known in either LOCAL or sublinear MPC models for graphs with low arboricity'; the related-work discussion would benefit from explicitly contrasting with the matching-only result of Behnezhad et al. [BBD+19] to make the novelty precise.","section":"Introduction, related work"}],"recommendation":"major_revision","confidential_remarks":"The LOCAL analysis (Theorem 9) is sound and is the strongest part of the paper. The MPC section has genuine but likely fixable gaps: the stratified estimator is wrong as written, the degree bound omits a factor of 4tau+1, and the sample count is not matched to the concentration lemma. These are not scope-level errors, so I recommend major revision rather than reject. The reliance on [GGM22] as a black box is acceptable; one coauthor is an author of that framework, but the paper cites it as a published result and does not derive it here."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the LOCAL result is real; the MPC result is not. I read Section 4 and Theorem 9 carefully, and the arboricity argument checks out: after τ ≈ log_{1+ϵ}(4λ/ϵ) rounds, the only way the algorithm can miss a 2+O(ϵ) approximation is if a large fraction of N(L_{2τ}) is served by L0, and that forces a subgraph of density ~λ that cannot exist. The proof of Lemma 7 and the use of capacity sums are sound. This is a genuine improvement over the O(log n) analysis of AZM18 for low-arboricity graphs. I would be comfortable citing that part.\n\nThe MPC section is where it falls apart. Lemma 11 as stated is false. The proof splits into \"small groups contribute little\" and \"large groups concentrate,\" but those two cases are not exhaustive, and the first case fails exactly when small groups carry a large total mass. A single high-weight element can be missed with high probability and the rescaled estimate is off by ~n/t^2. That is not just a gap in the proof; it is a counterexample to the claim. Since Lemma 11 is the concentration step that justifies the whole sampling scheme, the correctness of Algorithm 2 is not established.\n\nThe stress-test note about the (4τ+1) factor is also correct. Algorithm 2 samples t edges from each of 4τ+1 β-level groups per round, so the per-vertex degree in H_r is (4τ+1)t, not the d printed in the text. The B-radius volume bound d^B then misses a factor of (4τ+1)^B, which enters as B log τ = Θ(√logλ · log logλ) in the exponent. For asymptotic λ this might be absorbable by the constant in B, but the paper does not supply the argument, and for moderate λ the slack in eq. (4) is gone.\n\nThe rest of the MPC description is also under-specified: the graph exponentiation step is invoked as standard without saying whether the B-hop balls are taken in the union of the H_r or in each H_r separately, which affects the volume bound. These issues are fixable, but they require a real rewrite of Section 5 and Appendix A.\n\nVerdict: send to a good venue, but only with the expectation of major revision. The LOCAL theorem is worth publishing on its own, and the MPC approach may be salvageable, but the current main theorem is not supported. The paper is aimed at the MPC and sublinear-algorithms crowd; a referee with a taste for checking sampling arguments will earn their keep.","headline":"The LOCAL analysis is clean and likely correct, but the MPC algorithm rests on a false sampling lemma and a missing (4τ+1) factor, so the headline bound is not established.","tokens_in":23860,"tokens_out":10830,"would_cite":true,"duration_ms":100110,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W15","68W25","05C85","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"A new MPC algorithm computes near-optimal allocations on sparse graphs in $O(\\sqrt{\\log\\lambda}\\log\\log\\lambda)$ rounds, without knowing $\\lambda$.","keywords":["allocation problem","b-matching","Massively Parallel Computation","arboricity","LOCAL model","proportional allocation","graph sparsification","sublinear space"],"falsifier":"Take a star with arboricity $\\lambda=1$, center capacity $n-1$, and priorities arranged so one $\\beta$-level group contains a single neighbor with the maximum possible weight while all other neighbors are in the lowest group; run algorithm 2 with the stated sample size $t$. If the $t$ uniform samples miss that single high-weight element---probability roughly $1-t/(n-1)$---the estimated center aggregate is off by more than the promised $1+4\\epsilon$ factor, and the output should violate the claimed $2+16\\epsilon$ approximation for large $n$ and constant small $\\epsilon$.","tokens_in":22911,"feed_emoji":"⚙️","tokens_out":9568,"duration_ms":82916,"temperature":0.7,"pith_summary":"The paper targets the allocation problem: given a bipartite graph with capacities on the right-hand vertices, find the largest set of edges that respects those capacities. It proves that a known proportional-allocation LOCAL algorithm, previously analyzed as $O(\\log n)$ rounds, actually converges in $O(\\log \\lambda)$ rounds where $\\lambda$ is the graph's arboricity---the minimum number of forests into which its edges can be partitioned. Translating this analysis to the Massively Parallel Computation (MPC) model with sublinear per-machine memory gives an algorithm that runs in $O_\\epsilon(\\sqrt{\\log \\lambda}\\log\\log \\lambda)$ rounds, uses $\\tilde{O}(\\lambda n)$ total memory, achieves a $1+\\epsilon$ approximation, and does not need to know $\\lambda$ in advance. This is the first $o(\\log n)$-round sublinear-MPC algorithm for constant-approximate allocation on low-arboricity graphs, so it brings allocation close to the round bounds previously achieved only for matching.","feed_headline":"Allocation on sparse graphs solved in O(√log λ log log λ) MPC rounds","feed_subtitle":"The round count drops from log n to the arboricity log, and the algorithm never needs to know λ.","key_machinery":"The machine carrying the argument is the $\\beta$-value proportional update together with the level-set decomposition $L_j=\\{v:\\beta_v=(1+\\epsilon)^j\\beta_{\\min}\\}$. The critical identity is that after $\\tau$ rounds every edge from $N(L_{2\\tau})$ into $L_0$ contributes at most $1/(1+\\epsilon)^{2\\tau-2}$ of its neighbor's allocation, so if too much weight flows into $L_0$, the subgraph induced by $N(L_{2\\tau})\\cup L_0$ must contain $\\Omega(|N(L_{2\\tau})|(1+\\epsilon)^{2\\tau})$ edges, contradicting the arboricity upper bound. This converts a density bound into a round bound. For MPC, exact sums are replaced by estimates from $t=(1+\\epsilon)^{2B}\\epsilon^{-5}\\log n$ uniform samples per $\\beta$-level group per vertex, and graph exponentiation---doubling the neighborhood radius in each round---collects $B$-hop balls whose volume is controlled by the sample bound; choosing $B\\approx \\sqrt{\\log\\lambda}$ makes total memory $\\tilde{O}(\\lambda n)$.","core_discovery":"The central discovery is that the convergence speed of the proportional allocation algorithm depends on arboricity, not on graph size. The algorithm assigns each right vertex a priority $\\beta_v$, initially 1; in each round each left vertex splits its value among neighbors in proportion to their $\\beta$ values, and each right vertex raises or lowers $\\beta_v$ by a factor $1+\\epsilon$ when its load is too low or too high. After $\\tau$ rounds the right vertices fall into $2\\tau+1$ level sets $L_0,\\dots,L_{2\\tau}$ by $\\beta$ value. The paper shows that if the algorithm has not yet produced a $(2+O(\\epsilon))$-approximation, then almost all units sent from $N(L_{2\\tau})$ land in $L_0$; because $\\beta$ values at $L_{2\\tau}$ dominate those at $L_0$ by $(1+\\epsilon)^{2\\tau}$, each such edge can carry at most $\\epsilon/(4\\lambda)$, and the arboricity bound forces fewer than $2\\lambda|N(L_{2\\tau})|$ such edges. That contradiction yields $\\tau\\approx \\log_{1+\\epsilon}(4\\lambda/\\epsilon)+1$ rounds. In MPC the same dynamics are simulated over blocks of $B$ rounds using uniform samples from each $\\beta$-level group per vertex; graph exponentiation then collects the $B$-hop influencing neighborhood of every vertex, and a detectable stopping condition lets the algorithm double its guess of $\\lambda$ until it succeeds.","pith_inferences":["The same block-simulation idea likely extends to bipartite $b$-matching: each invocation of the boosting construction of [GGM22] works on a subgraph of arboricity at most $\\lambda$, so closing the small-group sampling gap would give an $o(\\log n)$-round sublinear-MPC algorithm for $b$-matching on sparse graphs, a question the paper leaves open.","The 'guess $\\lambda$ by doubling $\\sqrt{\\log\\lambda}$ and test a stopping condition' strategy is portable: any density-controlled local algorithm whose termination can be verified in $O(1)$ MPC rounds can run without knowing its density parameter at only constant factor overhead.","The per-group uniform sampling in lemma 11 is likely suboptimal for small groups; an importance-sampling or heavy-element correction could reduce the sample count and shrink the per-vertex degree bound and memory footprint beyond the stated $\\tilde{O}(\\lambda n)$."],"forward_implications":["On graphs of arboricity $\\lambda$, allocation can now be solved in $\\tilde{O}(\\sqrt{\\log\\lambda}\\log\\log\\lambda)$ MPC rounds with sublinear per-machine memory, improving on the previous $O(\\log n)$ translation of the local algorithm.","The underlying LOCAL protocol runs in $O_\\epsilon(\\log\\lambda)$ rounds and yields a $2+\\epsilon$ fractional allocation deterministically; boosting it to a $1+\\epsilon$ integral allocation preserves the same round complexity.","Because the algorithm does not need to know $\\lambda$, it can be run on any input; the stopping test that replaces $\\lambda$ costs only $O(1)$ MPC rounds.","The total memory $\\tilde{O}(\\lambda n)$ is near-linear for uniformly sparse graphs, so the algorithm also works in the near-linear-space MPC regime, not only the sublinear one.","The result avoids capacity-copy reductions that blow up arboricity (a star with capacity $n-1$ becomes a complete bipartite graph), so the sparse-structure guarantee is preserved."],"supporting_citations":[{"why":"Supplies the proportional allocation LOCAL algorithm whose convergence analysis is tightened from $O(\\log n)$ to $O(\\log \\lambda)$.","marker":"[AZM18]"},{"why":"Supplies the sparsification and graph exponentiation machinery used to simulate $B$ LOCAL rounds in $O(\\log B)$ MPC rounds.","marker":"[GU19]"},{"why":"Provides the framework that boosts the constant-factor approximation to $1+\\epsilon$ and the layer-graph reduction the final algorithm relies on.","marker":"[GGM22]"},{"why":"Introduces graph exponentiation, the technique used to gather $B$-hop neighborhoods.","marker":"[LW10]"},{"why":"Establishes the prior arboricity-sensitive round bounds for matching that this allocation result generalizes and improves.","marker":"[BBD+19]"}],"fun_headline_variants":["Sparse graph allocation: arboricity, not size, drives MPC round count","MPC allocation rounds: O(√log λ) for sparse graphs","Allocation in uniformly sparse graphs: speed scales with arboricity","Arboricity dictates allocation round count in MPC"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The MPC correctness argument rests on the claim that independent uniform samples from each $\\beta$-value group estimate the sums needed in every round to within a $1+O(\\epsilon)$ factor; the proof sketch does not fully control the possibly large contribution of a single high-weight element in a small group, and the per-vertex degree bound omits the factor from the number of $\\beta$-level groups, so the claimed ball-size and memory bounds are not established.","fun_headline_variants_meta":{"raw":{"variants":["Sparse graph allocation: arboricity, not size, drives MPC round count","MPC allocation rounds: O(√log λ) for sparse graphs","Allocation in uniformly sparse graphs: speed scales with arboricity","Arboricity dictates allocation round count in MPC"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000568,"raw_usage":{"total_tokens":2742,"prompt_tokens":1048,"completion_tokens":1694,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":664,"completion_tokens_details":{"reasoning_tokens":1628}},"tokens_in":664,"tokens_out":1694,"duration_ms":14781,"temperature":1.0,"reasoning_tokens":1628,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T10:42:32.484322+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a star with arboricity $\\lambda=1$, center capacity $n-1$, and priorities arranged so one $\\beta$-level group contains a single neighbor with the maximum possible weight while all other neighbors are in the lowest group; run algorithm 2 with the stated sample size $t$. If the $t$ uniform samples miss that single high-weight element---probability roughly $1-t/(n-1)$---the estimated center aggregate is off by more than the promised $1+4\\epsilon$ factor, and the output should violate the claimed $2+16\\epsilon$ approximation for large $n$ and constant small $\\epsilon$.","supporting_citations":[],"review_version":1}