{"id":"b10fc763-b528-4576-a05f-06a9fe3ccc85","arxiv_id":"2505.14250","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Near-optimal one- and two-round protocols for ℓp heavy hitters and Fp estimation in the coordinator and distributed tracking models, including the first near-optimal algorithms for tracking Fp.","lead":"This paper gives simple communication-efficient algorithms for finding heavy hitters and estimating frequency moments when data is spread across many machines. The algorithms nearly match known lower bounds in both static and dynamic distributed settings, resolving open problems for several cases.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The Fp tracking result depends on an unverified black-box: Lemma 2 asserts that Cormode et al. [10] give exact thresholded-sum tracking with O~(k) communication per phase, and if that primitive is only approximate or has hidden restrictions, Theorem 9 does not follow.","rationale":"The reader's weakest assumption points to the same load-bearing dependency: the exact thresholded-sum tracking algorithm of [10] is invoked without re-derivation, and the Fp tracking theorem collapses if that primitive is not exactly as assumed. I agree with that identification. I also reviewed the surrounding proofs for internal consistency. The static ℓp-HH results (Theorems 2, 3, 5) appear sound up to constant factors and standard union-bound/boosting steps. The recursive-sketching reductions for the coordinator model are standard, though Algorithm 6's top-(4p/α) selection is too small: the proof's own set S2 is bounded by 4^p/α, not 4p/α, so the cover may miss heavy hitters. This is a genuine but easily repairable constant-factor bug, and it does not affect the asymptotic communication claims because p is fixed. The Fp tracking result, however, depends on Lemma 2's black-box thresholded-sum routine. Exact thresholded-sum tracking with O~(k) communication per phase is plausible—one can imagine binary-search or threshold-assignment schemes—but the paper gives no details, and the correctness of the unbiased estimator in Algorithm 9 is sensitive to even small detection delay or error. Consequently, the paper should be accepted only conditionally on verification of that black-box, which is exactly the reader's conditional verdict. My stress-test does not move the verdict; it sharpens the condition that must be checked.","tokens_in":20623,"tokens_out":29665,"duration_ms":298944,"concrete_test":"Open Cormode, Muthukrishnan, and Yi (SODA 2008) and locate the exact thresholded-sum tracking result used as a black box in Algorithm 9. Verify three properties: (a) it detects a fixed threshold with zero error, not merely (1±ε) approximation; (b) it costs O(k polylog n) bits per active instance even when the threshold is arbitrary and the instance is restarted at phase boundaries; and (c) it can be run in parallel for multiple elements with the same underlying stream without additional communication cost. If any of these fail, Lemma 2 is invalid and Theorem 9 needs revision. If the exact statement is ambiguous, a second check is to simulate the primitive for k=2 with the adversarial pattern where one site receives T-1 updates before the other receives 1, and measure whether the claimed O(polylog n) bits per phase suffice to detect the crossing exactly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central Fp tracking bound (Theorem 9) is built on Algorithm 8/9, whose correctness and communication rely entirely on Lemma 2. In particular, Lemma 2.1 requires that ALG1 output 1 exactly when the global frequency v_j(t) first reaches (r + v_j^p(t_s))^{1/p}, so that w_j(t) is unbiased; Lemma 2.3 asserts the exact thresholded-sum tracking algorithm of [10] has communication O~(k) per phase. The paper does not state the precise guarantee of [10], does not prove it, and does not address how it composes with many simultaneous instances that are started and stopped at phase boundaries. This is the single most load-bearing assumption because every other part of the tracking proof (weak covers, round termination, total communication) reduces to it. If [10] in fact provides only (1±ε)-approximate sum tracking, or requires the threshold to be fixed for the entire stream, then the unbiasedness in Lemma 2 fails and the claimed O~(k^{p-1}/ε^2) tracking communication is unsupported. The concern is not that the result is necessarily false; it is that the paper's correctness is not self-contained at exactly the point where the tracking model differs from the static model. A secondary, repairable issue is that Algorithm 6 selects the top 4p/α estimates while the proof's own bounds give a set of size up to 4^p/α, so the cover may miss true heavy hitters; this affects the two-round Fp protocol but is fixable without changing the asymptotic claims.","agreement_with_reader":"agree"},"referee_report":null,"author_rebuttal":null,"desk_editor":null,"rs_alignment":null,"lean_confirmation":null,"pith_extraction":null,"created_at":"2026-08-07T15:38:27.068022+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":null,"supporting_citations":[],"review_version":1}