{"id":"82e43d86-b2b7-43db-858e-8a7a0f08552c","arxiv_id":"2506.07342","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"First sublinear-space one-pass linear sketches for top-k and trimmed-k frequency moments, with upper and lower bounds governed by a tail ratio condition.","lead":"This paper presents the first streaming sketches that estimate the F_p moment of the largest k coordinates and of the trimmed middle of a frequency vector in sublinear space, under a condition relating the k-th largest value to the tail. The authors also prove communication lower bounds and apply the method to estimate impact indices such as the h-index in polylogarithmic space.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claimed sharp structural threshold is unsupported: Theorem 4.1 and Lemma 8.1 leave an uncharacterized gap, so the abstract's 'if and only if' does not follow.","rationale":"The reader's weak point (Lemma 4.6) is a genuine but repairable constant-factor gap: the premise gives v ≥ a_k/(1+ε) rather than v ≥ a_k, which weakens the bound by a factor of at most (1+ε)^2 and can be absorbed into the existing poly(ε/log n) exponents without changing the algorithm's asymptotic space. The more serious issue is the paper's central structural claim, which the reader also noted in the rationale but did not make the primary concern. The abstract and Section 1.1 explicitly promise an 'if and only if' threshold determined by a_k^2 versus ||x_{-k}||_2^2/k, but the stated lower bound condition (with the extra k/n factor) is far stronger than the complement of the upper-bound condition. This leaves an exponentially large regime where no result applies, so the 'sharp threshold' is not a threshold at all. Because this concern attacks the paper's headline contribution rather than a fixable lemma, it is the most load-bearing. The algorithmic contribution itself—a poly(log n/ε)-space sketch under the explicit condition of Theorem 4.1—appears plausible and valuable, which is why the appropriate verdict remains CONDITIONAL/UNCHANGED: the paper should be accepted only after the structural characterization is corrected to an honest one-sided claim or a matching lower bound is supplied.","tokens_in":31850,"tokens_out":18254,"duration_ms":178159,"concrete_test":"Exhibit a concrete vector family in the gap: take n=2^20, k=2^10, set the top k coordinates all equal to A with A^2 = (k/n)^{1/2}·||x_{-k}||_2^2/k, and let the remaining coordinates be uniformly small so that ||x_{-k}||_2^2/k = A^2·(n/k)^{1/2}. Check the two conditions: A^2/(||x_{-k}||_2^2/k) = (k/n)^{1/2} ≈ 2^{-5}, whereas Theorem 4.1 requires ≥ (ε/log n)^c and Lemma 8.1 requires ≤ c·(k/n) ≈ c·2^{-10}. For ε=0.1 and c<1/2, neither holds. If no theorem or remark in the paper covers this (or any analogous) instance with a space bound, the claimed sharp threshold is not established.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's headline contribution is a sharp structural threshold: poly(log n/ε)-space estimation of the top-k F_p moment is claimed to be possible exactly when a_k^2 is at least poly(ε/log n)·||x_{-k}||_2^2/k. The formal statements do not establish this. Theorem 4.1 gives an upper bound under a_k^2 ≥ (ε/log n)^c·||x_{-k}||_2^2/k. The lower bound, Lemma 8.1, applies only when a_k^2 ≤ c·(k/n)·||x_{-k}||_2^2/k (or c·(k/n^c) with c∈(0,1) in Corollary 8.5). For moderate k, (k/n) is much smaller than (ε/log n)^c, so the two conditions are not complementary: in the regime c·(k/n)·||x_{-k}||_2^2/k < a_k^2 < (ε/log n)^c·||x_{-k}||_2^2/k, neither bound applies and the space complexity is left open. The construction in Lemma 8.1 also appears to violate its own premise in the natural parametrization: for the 2-SUM instance, a_k^2 is roughly (k/n)·||A_{-k}||_2^2/k, so the required a_k^2 ≤ c·(k/n)·||A_{-k}||_2^2/k with c<1 fails; the reduction only works for the padded variant in Corollary 8.5, which is a much weaker condition. This does not invalidate the algorithmic upper bound (the constant-factor gap in Lemma 4.6 flagged by the reader is repairable), but the central 'sharp iff' claim is a significant overstatement.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript studies one-pass linear sketching of the F_p moment of the top-k coordinates and of the trimmed-k vector (the vector obtained by deleting the largest and smallest k entries). For p in [0,2], it gives a level-set and sub-sampled Count-Sketch algorithm (Theorem 4.1, Section 4) that, under the tail condition a_k^2 >= (eps/log n)^c * ||x_-k||_2^2 / k, estimates the top-k F_p moment to (1 +/- eps) in poly(log n / eps) space, and a similar trimmed-k estimator with an additional additive error term (Theorem 5.1). Theorems 6.1 and 6.4 extend the results to p > 2 with a factor n^{1-2/p}. Section 7 derives applications to thresholded F_p and to g-, h-, and a-index moments, claiming an improvement over the h-index algorithm of Govindan, Monemizadeh, and Muthukrishnan. Section 8 gives lower bounds: Lemma 8.1 claims Omega(eps^{-2} n/k) space when a_k^2 <= c (k/n) ||x_-k||_2^2 / k, Lemma 8.6 an Omega(n/k^3) bound for O(k^p) approximation, and Lemma 8.11 an Omega(eps^{-2} log k) bound for the trimmed-k additive error. Section 9 reports experiments on synthetic, AOL, and CAIDA data.","tokens_in":32126,"tokens_out":30511,"duration_ms":301403,"significance":"If the upper-bound theorems are correct, the paper makes a useful contribution: it is the first to show that the top-k and trimmed-k F_p moments can be estimated in poly(log n / eps) space when the k-th order statistic dominates the average tail energy, and the multi-level residual comparison in Lemmas 4.3 and 5.5 is a genuine technical idea. The applications to thresholded F_p and impact indices, together with the experimental comparison against Count-Sketch, add value. However, the headline claim of a sharp structural 'if and only if' threshold is not supported by the lower-bound results as written: Lemma 8.1 is not proved in its stated regime, and Lemma 8.11 addresses the residual norm rather than the trimmed-k sum. The conditional algorithmic results remain significant, but the paper's advertised characterization is currently an overstatement.","major_comments":[{"comment":"The sharp-threshold claim is not established. Theorem 4.1 gives poly(log n / eps) space when a_k^2 >= (eps/log n)^c ||x_-k||_2^2 / k (Eq. 2). Lemma 8.1 claims Omega(eps^{-2} n/k) space when a_k^2 <= c (k/n) ||x_-k||_2^2 / k, but the 2-SUM construction in its proof does not satisfy this premise: in the constructed vector A, all nonzero entries are k/2 or k and the total number of nonzero entries is at most (2-c_0)k for the constant fraction c_0 of intersecting pairs, so U - k is O(k), and a_k^2 <= c (k/n) ||A_-k||_2^2 / k would force n = O(U - k), contradicting k <= 0.1n. Only the padded Corollary 8.5, with k/n^c in place of k/n for c < 1, follows; that condition is far weaker than the upper-bound condition. The gap between (eps/log n)^c * tail/k and c' (k/n^c) * tail/k is uncharacterized, so the 'if and only if' language in the abstract and Section 1.1 is unsupported.","section":"§8.1.1, Lemma 8.1 and Corollary 8.5; abstract and §1.1"},{"comment":"The lower bound stated for the trimmed-k moment is actually about the residual norm. Lemma 8.11 concerns ||x_-k||_p^p, i.e., the vector after deleting only the top k coordinates, whereas Section 5 defines the trimmed-k statistic as sum_{i=k}^{n-k} |a_i|^p after deleting both the largest and smallest k coordinates. In the Gap-Hamming reduction with Delta(a,b)=k and Delta=k+eps k, the vector x - y has m = k or k + eps k nonzero entries of magnitude B; since m < 2k for eps < 1, deleting the top k and bottom k entries leaves the zero vector in both cases. The construction therefore cannot distinguish the two cases for the trimmed-k sum, and the claimed unavoidability of the additive term eps k |a_{k-eps k}|^p is not proven.","section":"§8.2, Lemma 8.11"},{"comment":"The proof of Lemma 4.6 relies on the inequality v >= a_k in Lemma 4.3 (Eq. 3), but the premise zeta(1+eps)^{t-j} >= |a_k| together with v = zeta(1+eps)^{t-j-1} only implies v >= |a_k|/(1+eps). This introduces a (1+eps)^{p-2} factor into the bound s_j v^2 >= (eps/log n)^{c+2} ||x_-k||_2^2 and propagates to the tail-error estimate in Lemma 4.6. The gap is a constant factor that can likely be absorbed by adjusting the exponent c, but as written the derivation does not yield the stated lemma, and Theorem 4.1 depends on it.","section":"§4, Lemma 4.6 and Eq. (3)"},{"comment":"Remark 4.1 asserts that condition (2) is always met when k >= polylog n. This is false. For a vector with k - 1 coordinates equal to M and n - k + 1 coordinates equal to 1, one has a_k = 1 and ||x_-k||_2^2 is about n, so (2) becomes 1 >= (eps/log n)^c (n - k)/k, which fails when n/k is super-polylogarithmic, e.g., when k = polylog n. The correct moderately-large regime appears to be k >= n/polylog n, as stated in the introduction; the remark as written contradicts that and should be corrected.","section":"§4, Remark 4.1"},{"comment":"The advertised improvement for the h-index over Govindan, Monemizadeh, and Muthukrishnan is stated unconditionally, for example 'when h = n^{1/3} ... our algorithm achieves O(poly(log n/eps)) bits', but Corollary 7.6 requires a_{(1+eps)k}^2 >= (eps/log n)^c ||x_{-(1+eps)k}||_2^2 / k. For a natural h-index vector in which the top h coordinates equal h and the remaining coordinates equal h - 1, this condition becomes h^2 >= (eps/log n)^c * n h, which fails when h = n^{1/3}. The h-index comparison is therefore only valid under an additional heavy-tail assumption that is not part of the h-index definition, and the claimed improvement should be stated conditionally.","section":"§7.2.2, Corollary 7.6 and §1.1"},{"comment":"The set-disjointness reduction assumes that in the disjoint case the vector x is (1,1,...,1) and that ||x_-k||_2^2 = n - k. This requires that the players' sets cover the entire universe [m], which is not part of the k-player set-disjointness promise in Lemma 8.7. When some coordinates are covered by no player, the top-k entries can include zeros and the claimed values of a_k and ||x_-k||_2^2 are not correct; the Omega(n/k^3) bound is therefore not derived as written.","section":"§8.1.2, Lemma 8.6"}],"minor_comments":[{"comment":"The pseudocode uses 'poly(eps/L) heavy hitters', which is inconsistent with the (log n/eps)^{c+9} bucket count used in Lemma 4.6 and in the surrounding text; the notation should be unified.","section":"§4, Algorithm 1 line 6"},{"comment":"There are typos: 'k-plyaer' should be 'k-player' in Section 8.1.2, and 'Holder' should be 'Hölder' in Section 6.","section":"§8.1.2 and §6"},{"comment":"The proof says 'There are log m / O(eps) level sets' but then uses log^2 n in the bound; since m = poly(n), this is O(log n/eps), and the denominator should be written consistently.","section":"§4, Lemma 4.8"},{"comment":"The text refers to Figure 1, but the figure appears not to be included in the manuscript text; ensure the figure is present in the submitted version.","section":"§9, Figure 1"},{"comment":"In Definition 2.1, the heavy-hitter structure is defined with a parameter k that is unrelated to the k in the main theorems; the reader must guess which k is meant. Clarify by using a different parameter name, such as t.","section":"§2, Definition 2.1"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The algorithmic core is real and likely correct: this is the first sublinear-space streaming treatment of top-k and trimmed-k F_p moments for p in [0,2], under an explicit tail condition. The multi-level subsampling with residual-norm comparisons across adjacent levels is a genuine technical step, and the h-index improvement over Govindan-Monemizadeh-Muthukrishnan is concrete. The upper-bound proof is broadly plausible; the constant-factor gap in Lemma 4.6 (v >= a_k/(1+eps) versus v >= a_k) is annoying but repairable.\n\nThe trouble is the advertised \"sharp structural threshold.\" The abstract and Theorem 4.1/Lemma 8.1 together claim an if-and-only-if characterization, but the upper condition is a_k^2 >= poly(eps/log n)*||x_{-k}||_2^2/k, while the lower bound only applies when a_k^2 <= c*(k/n)*||x_{-k}||_2^2/k. For moderate k these conditions are not complementary; there is a large middle regime where neither bound applies and the space complexity is open. The stress-test note is right: the Lemma 8.1 construction appears to violate its own premise in the natural parametrization, since the 2-SUM instance gives a_k^2 roughly (k/n)*tail/k, so the c<1 condition fails. The padded Corollary 8.5 works only under a much weaker condition, which does not support the abstract's \"if and only if.\"\n\nTwo smaller issues compound this. Remark 4.1 is false as written: k >= polylog n does not imply condition (2) for all vectors; the tail can still dominate. And Lemma 8.11 lower-bounds the residual norm after removing the top-k, not the trimmed-k sum defined in Theorem 5.1, so the claimed unavoidable additive error term is not established.\n\nThe citations are fine. [12] is a published communication lower bound, used as a black box; [36] is self-cited but the paper does not construct anything that reduces to that work's target. No circularity problem. The experiments are basic but honest, and they do show the algorithm beating plain Count-Sketch at the same bucket budget.\n\nThis paper deserves a serious referee. The algorithmic contribution is valuable and probably correct. But the headline claim needs to be scaled back to \"upper and lower bounds with a gap\" or the gap must be filled. I would send it to review with a demand to fix the threshold statement, repair Remark 4.1, and align the trimmed-k lower bound with the theorem's statistic.","headline":"Genuine sublinear-space algorithms for top-k and trimmed-k F_p moments, but the sharp 'if and only if' threshold is overstated and the lower-bound section needs repair.","tokens_in":32738,"tokens_out":1915,"would_cite":true,"duration_ms":22148,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W20","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper establishes that the top-k F_p moment of a frequency vector can be estimated in poly(log n/eps) space exactly when the k-th largest entry dominates the average squared tail, with matching upper and lower bounds.","keywords":["streaming algorithms","frequency moments","top-k F_p moment","trimmed statistics","linear sketches","heavy hitters","Count-Sketch","h-index"],"falsifier":"Run the level-set estimator on a vector engineered to sit at the threshold, with $a_k^{2}$ equal to (eps/log n)^c times the average squared tail and a contributing level set whose lower endpoint equals a_k/(1+eps), and check whether the estimated level size stays within (1±eps) of the true count. A miss of even one surviving coordinate in that level would violate the paper's key lemma and the theorem's guarantee. Alternatively, feed the 2-SUM hard instance from the paper's lower bound to any poly(log n/eps)-space sketch; if it returns a (1±eps) answer, the claimed $\\Omega$($eps^{{-2}}$ n/k) lower bound is false.","tokens_in":31565,"feed_emoji":"📊","tokens_out":7460,"duration_ms":74018,"temperature":0.7,"pith_summary":"This paper asks whether order-based statistics of a frequency stream, specifically the sum of the p-th powers of the k largest entries and the sum after discarding the largest and smallest k entries, can be approximated in sublinear space. It answers yes for p in [0,2], giving linear sketches that use poly(log n/eps) bits whenever k is moderately large, and more generally whenever the k-th largest value dominates the average squared tail. The paper also proves this dominance condition is essentially sharp, with a lower bound of $\\Omega$($eps^{{-2}}$ n/k) bits when the k-th largest value is too small. These are the first sublinear-space algorithms for trimmed F_p statistics, and they improve the space needed for impact indices such as the h-index.","feed_headline":"Top-k moments now sketchable in poly-log space","feed_subtitle":"A single ratio—the k-th largest value versus the average tail—decides when sublinear space is possible.","key_machinery":"The engine is a multi-level subsampling scheme combined with a level-set decomposition. Coordinates are grouped into exponentially growing intervals [zeta(1+eps)^{t-j-1}, zeta(1+eps)^{t-j}) with a random offset zeta, and for O(log n) subsampling rates the algorithm maintains an $\\ell^2$ heavy-hitter structure, implemented as a small Count-Sketch, on the subsampled stream. For each contributing level set it finds the coarsest subsampling level at which about Theta(log n/$eps^{2}$) survivors appear, estimates the level size by re-scaling the survivor count, and sums the estimated contributions. The analytical novelty is a refined multi-level comparison showing that the threshold condition on $a_k^{2}$ forces each contributing level to dominate the residual norm after rank(v), so the Count-Sketch tail error stays below the level value v and every surviving heavy coordinate is identified.","core_discovery":"The paper's central claim is that sublinear-space approximation of the top-k F_p moment for p in [0,2] is governed by a single ratio: compare $a_k^{2}$, the square of the k-th largest absolute frequency, with ||x_{-k}||$_2^{2}$ / k, the average squared tail mass. When $a_k^{2}$ >= (eps/log n)^c * ||x_{-k}||$_2^{2}$ / k, the level-set estimator returns a (1±eps) approximation of sum_{i=1}^k |a_i|^p using poly(log n/eps) bits, and the condition is automatically satisfied for k >= n/polylog n. When instead $a_k^{2}$ <= c*(k/n)*||x_{-k}||$_2^{2}$/k, any O(1)-pass streaming algorithm requires $\\Omega$($eps^{{-2}}$ n/k) bits, so the threshold is structurally sharp. The trimmed-k statistic is computed by subtracting two top-moment estimates made on the same level sets, which cancels the top contribution and leaves an unavoidable additive error of O(eps)*(sum_{i=k}^{n-k} |a_i|^p + k|a_{k-eps k}|^p). For p>2 the same algorithms carry an extra $n^{{1-2/p}}$ factor that matches the known lower bound for global F_p estimation.","pith_inferences":["If the threshold characterization extends in the natural way, the same ratio of the k-th largest value to the average squared tail is likely to govern other order-based streaming statistics, such as relative-error approximations of arbitrary order statistics, which the paper does not address.","The 2-SUM reduction suggests a two-party communication analogue of the result: the same n/k threshold should characterize the communication cost of approximating top-k moments in distributed settings, a consequence the paper leaves implicit.","A practical extension is an adaptive sketch that tests the threshold condition online and switches from poly-log space to a larger Count-Sketch when the data violate it, since the experiments indicate the constant factors are small on skewed data.","One can probe the constant-factor gap in the level-set analysis directly by building a vector whose contributing level set starts at v = a_k/(1+eps); if survivors are missed there, the poly(eps/log n) exponent in the condition may be reducible."],"forward_implications":["For k >= n/polylog n, the dominance condition is automatically met, so the top-k F_p moment for p in [0,2] can be estimated in poly(log n/eps) bits with no additional assumption on the tail.","When the F_p mass of the top k coordinates is comparable to that of the tail, the same estimate gives a (1±eps) estimate of the k-residual error, improving the earlier residual-error sketch by a k^{2/p} factor.","The algorithm yields poly(log n/eps)-space estimators for thresholded F_p sums and for the g-, h-, and a-indices, including a (1±eps) approximation of the h-index that improves on prior space bounds that scale polynomially with n.","For p>2, the same multi-level sketches require poly(log n/eps)*n^{1-2/p} bits, and the n^{1-2/p} factor is provably unavoidable.","Because the sketches are linear, they extend to distributed and mergeable streaming settings without additional passes."],"supporting_citations":[{"why":"Supplies the Count-Sketch heavy-hitter structure whose tail-error guarantee the multi-level estimator uses at each subsampling rate.","marker":"[11]"},{"why":"Introduces the level-set framework of exponentially growing intervals that the algorithms reuse for trimmed statistics.","marker":"[25]"},{"why":"Provides the 2-SUM communication problem reduced to in the lower-bound proof for small a_k.","marker":"[12]"},{"why":"The previous streaming algorithm for the h-index whose space bound the new algorithm improves to poly(log n/eps).","marker":"[21]"},{"why":"Defines the F_p frequency-moment problem whose trimmed variants are the subject of the paper.","marker":"[1]"},{"why":"Gives the prior residual-error sketching bound that the top-k estimator improves by a k^{2/p} factor in the comparable-mass regime.","marker":"[34]"},{"why":"Establishes the tight lower bound showing the n^{1-2/p} factor is necessary for p>2.","marker":"[35]"},{"why":"Defines the h-index used as the motivating impact metric in the applications.","marker":"[23]"}],"fun_headline_variants":["Sharp ratio decides when top-k moments fit in sublinear space","First sublinear-space sketches for trimmed F_p moments","Streaming top-k moments: poly-log space wins","Improved h-index estimation via sketching trimmed stats","One ratio rules top-k moment sketching"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument depends on the sub-sampled Count-Sketch being strong enough to identify every surviving coordinate of every contributing level set; if the tail error after subsampling is even slightly too large relative to the level value, the estimated level sizes and the final moment are no longer (1±eps)-accurate.","fun_headline_variants_meta":{"raw":{"variants":["Sharp ratio decides when top-k moments fit in sublinear space","First sublinear-space sketches for trimmed F_p moments","Streaming top-k moments: poly-log space wins","Improved h-index estimation via sketching trimmed stats","One ratio rules top-k moment sketching"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000196,"raw_usage":{"total_tokens":1394,"prompt_tokens":1009,"completion_tokens":385,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":625,"completion_tokens_details":{"reasoning_tokens":312}},"tokens_in":625,"tokens_out":385,"duration_ms":4180,"temperature":1.0,"reasoning_tokens":312,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:38:23.583431+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the level-set estimator on a vector engineered to sit at the threshold, with $a_k^{2}$ equal to (eps/log n)^c times the average squared tail and a contributing level set whose lower endpoint equals a_k/(1+eps), and check whether the estimated level size stays within (1±eps) of the true count. A miss of even one surviving coordinate in that level would violate the paper's key lemma and the theorem's guarantee. Alternatively, feed the 2-SUM hard instance from the paper's lower bound to any poly(log n/eps)-space sketch; if it returns a (1±eps) answer, the claimed $\\Omega$($eps^{{-2}}$ n/k) lower bound is false.","supporting_citations":[{"cited_title":"Chen, and Martin Farach-Colton","cited_arxiv_id":null,"evidence_quote":"Supplies the Count-Sketch heavy-hitter structure whose tail-error guarantee the multi-level estimator uses at each subsampling rate."},{"cited_title":"Woodruff, and Jason Zhang","cited_arxiv_id":null,"evidence_quote":"Provides the 2-SUM communication problem reduced to in the lower-bound proof for small a_k."},{"cited_title":"Woodruff","cited_arxiv_id":null,"evidence_quote":"Gives the prior residual-error sketching bound that the top-k estimator improves by a k^{2/p} factor in the comparable-mass regime."},{"cited_title":"Woodruff","cited_arxiv_id":null,"evidence_quote":"Establishes the tight lower bound showing the n^{1-2/p} factor is necessary for p>2."}],"review_version":1}