{"id":"6753f1c9-3900-480f-bf6e-01a00a6d9f50","arxiv_id":"2504.21175","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"F_p moment estimation and heavy-hitters in the sliding window model can be solved in Õ(ε^{-p} log^2 n + ε^{-2} log n) bits, matching the new lower bounds up to log log n and log(1/ε) factors.","lead":"This paper gives nearly optimal memory bounds for estimating frequency moments and finding heavy hitters on the most recent n items of a data stream. It closes a logarithmic gap left by prior sliding-window algorithms, which matters for network monitoring and log analysis at scale.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The stated F_p lower bound contradicts the trivial exact algorithm, so Theorem 1.3 cannot hold as written.","rationale":"The reader's identified concern about StitchSW mixing ell_p norms and F_p moments is real but reparable: raising the Indyk norm estimate to the p-th power (or defining g as an F_p estimate) would fix the units. The lower bound problem is more serious because it makes a stated main theorem false in an allowed parameter regime, and no local correction to Algorithm 2 can repair it. The trivial exact algorithm is decisive: for p=2, U=n, and epsilon=n^{-1/2}, Theorem 1.3 requires Omega(n log^2 n) bits, exceeding the O(n log n) bits needed to store the whole window. Moreover, the reduction's own counting shows the stream cannot encode the claimed amount of input information. Since the paper's central claim includes tightness, this contradiction warrants rejection of the paper as submitted, even if the upper-bound algorithm may be salvageable.","tokens_in":24367,"tokens_out":23407,"duration_ms":252846,"concrete_test":"Run the following check: instantiate Theorem 1.3 with p=2, U=n, and epsilon=n^{-1/2}; compare the stated lower bound Omega(n log^2 n) with the space O(n log n) of the exact trivial algorithm that stores the last n items. If the lower bound is larger, Theorem 1.3 conflicts with a valid algorithm. Additionally, for this instantiation in Lemma 5.3, count the total input bits k * r * log N against the total information in the constructed stream, about n log U bits; if the former exceeds the latter, the reduction cannot be correct.","verdict_should_be":"REJECT","load_bearing_attack":"In the fixed-window sliding-window model, a trivial algorithm stores the multiset of the current window's n items and answers any F_p query exactly, using O(n log U) bits. Theorem 1.3 asserts that for n >= U and epsilon >= n^{-1/p}, any algorithm needs Omega(epsilon^{-p} log^2(epsilon U) + epsilon^{-2} log(epsilon^{1/p} U)) bits. Instantiate p=2, U=n, and epsilon=n^{-1/2}. Then the first term is Omega(n log^2 n), while the trivial exact algorithm uses O(n log n) bits. Since the paper assumes U <= poly(n), this is an internal contradiction: the lower bound exceeds the information needed to store the entire input window. The source is the reduction in Lemma 5.3: it encodes k = epsilon^{-p} heavy-item positions per block across r blocks, each position among N options, which requires k r log N input bits. But the constructed stream has only O(n) elements and hence O(n log U) bits of information. For the parameter choices intended to yield log^2 n, k r log N is asymptotically larger than O(n log U), so the IndexGreater input cannot be embedded in the stream. Thus the tightness claim is false as stated, independently of the norm-versus-moment issue in Algorithm 2.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the sliding-window model for insertion-only streams and gives new bounds for two problems: F_p moment estimation (1 < p ≤ 2) and ℓ_p heavy hitters (0 < p ≤ 2). The main algorithmic contribution is an F_p moment estimation algorithm with space Õ(ε^{-p} log^2 n + ε^{-2} log n) bits for any fixed window, improving on the previous Õ(ε^{-2} log^3 n) bound. The main theoretical tool is a 'Strong Estimator' that gives uniform accuracy guarantees over all sub-windows, thereby avoiding the union-bound overhead that caused an extra logarithmic factor in prior work. The authors also claim a lower bound Ω(ε^{-p} log^2 n + ε^{-2} log n) for F_p estimation, up to log log n and log(1/ε) factors, via a reduction from an IndexGreater communication game. Finally, they combine their F_2 estimator with known heavy-hitters reductions to obtain a near-optimal ℓ_p heavy-hitters algorithm on sliding windows.","tokens_in":24554,"tokens_out":21638,"duration_ms":194132,"significance":"If the technical issues are repaired, the paper's results are significant: they close a logarithmic gap in sliding-window F_p moment estimation, introduce a reusable Strong Estimator concept, and give the first near-tight heavy-hitters algorithm in this model. The paper is unusually complete in its appendix proofs and carefully separates single-query guarantees from all-times tracking. The claimed space bounds depend on known prior work (WZ22, JW23, BGL+18, BDN17) used as black boxes, but the new tools—Strong Estimator, rotating random sets, and the windowed rounding procedures—are the paper's own contributions. The lower-bound reduction is a clean application of a standard communication game and, once the statement is corrected, should provide a useful template for future sliding-window lower bounds.","major_comments":[{"comment":"Algorithm 2's StitchSW function sets X ← g(t1,t), where g is defined in Algorithm 1 as the Indyk p-stable sketch's estimate of the ℓ_p norm ‖x(t1,t)‖_p, while each Y_j is a sum of difference estimators that estimate F_p moments (additive approximations to F_p(t1,j,k-1,t) − F_p(t1,j,k,t)). The output Z = X − Σ_j Y_j therefore mixes ℓ_p and F_p quantities, and the proof of Lemma 4.22 silently treats X as an estimate of the F_p moment of the prefix u. This is a load-bearing inconsistency in the central upper-bound theorem (Theorem 4.14). The fix is straightforward—define X as (g(t1,t))^p, or equivalently redefine g to output the F_p moment—and the constants in the analysis would need to be adjusted accordingly, but as written the algorithm and its correctness proof do not match.","section":"Sec. 4.4, StitchSW and Lemma 4.22"},{"comment":"The 'in particular' lower bound Ω(ε^{-p} log^2(ε U) + ε^{-2} log(ε^{1/p} U)) for n ≥ U is internally inconsistent with the trivial exact algorithm that stores the current window (O(n log U) bits). Taking p=2, U=n, and ε=n^{-1/2} gives the claimed bound Ω(n log^2 n), which exceeds O(n log n) by a log n factor. The reduction in the proof supports only the weaker expression with log^2(ε U^{1/p}) (or, with the parameter choices in Lemma 5.3, k r log N = Θ(n (ε n^{1/p})^{-(p+1)/2} log(ε n^{1/p}))), so the theorem statement as written is false. The statement needs to be corrected to match the proof, and the apparent contradiction with the trivial upper bound should be resolved explicitly.","section":"Theorem 1.3 and Theorem 5.4"},{"comment":"The proof states: 'We use Algorithm 1 to obtain a 1/2 approximation over ℓ^W_p, the rest of the proof follows by Lemma 2.5 and Lemma 2.6.' Lemma 2.5 requires a constant-factor approximation of the ℓ_2 norm within the window, not the ℓ_p norm. To make the argument valid, one must run Algorithm 1 with parameter p=2 to obtain an ℓ_2 approximation (which costs O(log^2 n) bits for constant accuracy), then invoke Lemma 2.5 with accuracy parameter ε^{p/2} before applying Lemma 2.6. As written, the cited lemmas do not combine to give the claimed conclusion for general p.","section":"Sec. 3.2, proof of Theorem 3.6"},{"comment":"The proof of the rounding-error bound for the Difference Estimator uses the inequality Π_{j=q(i−1)+1}^{qi}(|(Av)_j| + ε′‖v‖_p)^{p/q} ≤ Π_j |(Av)_j|^{p/q} + (ε′‖v‖_p)^{p/q}. This inequality does not follow from the stated bound |(Av)_j| ≤ λ‖v‖_p: expanding the product produces cross terms of the form (ε′‖v‖_p)^{c}(product of original entries)^{p/q−c}, and the assumption ε′ < 1/λ^2 does not by itself control these terms. Since Lemma 4.13 is used to justify the compressed storage of the Difference Estimators, the proof needs a more careful expansion or a different bound before the space claim in Lemma 4.23 is established.","section":"Sec. 4.3, proof of Lemma 4.13"}],"minor_comments":[{"comment":"The phrase 'u, v be 2 frequent vector' should be corrected to 'two frequency vectors'.","section":"Sec. 4.3, Lemma 4.13 statement"},{"comment":"The window is defined as [t−n+1, t] in Section 1.1, but Lemma 4.15 and Theorem 4.14 use W = [r−n, r]; the off-by-one convention should be made consistent throughout.","section":"Sec. 1.1 and Sec. 4.4"},{"comment":"The proof writes that the algorithm uses an (ε^p/64, ε^p/64, δSE) Strong Estimator 'for ε = 1/2'; the top-level partition uses the parameter ε0 = 1/2, so the notation should be clarified to avoid confusion with the final approximation parameter ε.","section":"Sec. 4.4, Lemma 4.15 proof"}],"recommendation":"major_revision","confidential_remarks":"The main results are significant and likely correct after revision, but two issues are load-bearing: the StitchSW norm/moment mismatch affects the central upper-bound theorem, and the stated lower-bound formula contradicts the trivial algorithm. Both are fixable locally (raise the Indyk estimate to the p-th power; correct the log exponent in the theorem statement), so I do not recommend rejection. The heavy use of coauthored prior work as black boxes is acceptable given that those papers are published, though the exposition would benefit from a short statement of which new ingredients are needed from each. The rotating-random-sets argument in Lemma 4.11 is terse and should be expanded for the camera-ready version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe upper-bound half here is the real news. The Strong Estimator, the rotating-random-sets trick, and the rounded difference estimators combine to break the log^3 n barrier for sliding-window F_p estimation, and the claimed O(ε^{-p} log^2 n + ε^{-2} log n) space is a genuine advance. The heavy-hitters application is straightforward once you have a constant-factor ℓ_2 window estimate, and the writing on why the union bound can be avoided is the most valuable part.\n\nThe lower-bound theorem as stated, however, is wrong. With p=2, U=n, and ε=n^{-1/2}, Theorem 1.3 claims Ω(n log² n) bits, but storing the current window's multiset costs O(n log n) bits and answers any F_p query exactly. That is a direct contradiction. The reduction in Lemma 5.3 doesn't produce the claimed bound at those parameters: the chosen 2r and N make N=Θ(1), so the lower bound is Ω(n), not Ω(n log² n). The log² term is not supported. This matters because \"tight\" is the headline claim.\n\nThere is also an incoherence in Algorithm 2's StitchSW: it subtracts F_p difference estimates from X=g(t1,t), where g is defined as an Indyk p-stable estimate of the ℓ_p norm. You cannot subtract moment differences from a norm estimate. Lemma 4.22 just uses g as if it were an F_p moment. Likely a one-line fix (set g to the p-th power), but as written it's broken.\n\nLemma 4.13's rounding proof is hand-wavy, and the notation overloads N. Those are minor compared to the above.\n\nThe upper-bound technique deserves a serious referee; it could be a strong paper after cleanup. The lower bound must be repaired or the paper reframed. I'd send it to review, but I would not cite it as is.","headline":"Strong new upper-bound technique for sliding-window F_p estimation, but the stated lower bound is false as written and the main algorithm mixes ℓ_p and F_p estimates.","tokens_in":25172,"tokens_out":9713,"would_cite":false,"duration_ms":92258,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Sliding-window $F_p$ moment estimation is settled up to $\\log\\log n$ and $\\log(1/\\varepsilon)$ factors, with heavy hitters following as a consequence.","keywords":["sliding window model","F_p moment estimation","heavy hitters","streaming algorithms","p-stable sketches","difference estimator","space lower bounds","strong estimator"],"falsifier":"Set $p=2$ and take the query window $W$ to contain a single distinct item once, so $F_2^W=1$. Let the stream before the window contain many copies of another item, so the suffix from the first retained timestamp has a much larger $F_2$ value. Interpret the base sketch output $X$ literally as the $\\ell_2$-norm estimate the pseudocode defines; then $Z=X-\\sum_j Y_j$ is an $\\ell_2$-norm quantity minus $F_2$-difference estimates, which will not be close to $1$. Running Algorithm 2 on this small stream and inspecting $Z$ decides whether the proof's unstated replacement of an $\\ell_2$ estimate by an $F_2$ estimate is merely notational.","tokens_in":24108,"feed_emoji":"📊","tokens_out":12882,"duration_ms":111195,"temperature":0.7,"pith_summary":"The paper tries to settle the space complexity of two classic streaming problems—estimating the $p$-th frequency moment $F_p$ and finding heavy-hitters—when queries are made only about the most recent $n$ items, the sliding window model. It gives an algorithm that approximates $F_p$ on any fixed window of size $n$ to within a $(1\\pm\\varepsilon)$ factor using $\\tilde{O}(\\varepsilon^{-p}\\log^2 n + \\varepsilon^{-2}\\log n)$ bits of space, for $1<p\\le 2$, and proves a lower bound showing this is optimal up to $\\log\\log n$ and $\\log(1/\\varepsilon)$ factors. As a consequence, it obtains an $\\tilde{O}(\\varepsilon^{-p}\\log^2 n)$-bit algorithm for $\\ell_p$ heavy-hitters on an arbitrary window, matching the known lower bound. A reader should care because previous algorithms carried an extra $\\log n$ factor that came from requiring many independently correct sketches; the paper removes that factor with a new estimator that is correct simultaneously on all sub-windows without a union bound, plus a rounding technique that compresses sketches.","feed_headline":"Sliding-window F_p estimates are tight to log-log factors","feed_subtitle":"New algorithms match lower bounds for F_p moments and heavy hitters on any window of size n.","key_machinery":"The load-bearing object is the Strong Estimator (Definition 2.2): a p-stable random matrix whose median-of-absolute-entries estimate $f_p(x_{(a,b)})$ is guaranteed, with probability $1-\\delta$, to be within $(1\\pm\\epsilon_1)\\ell_{p}^{(a,b)}\\pm\\epsilon_2 \\ell_p^{(l,r)}$ for every sub-window $[a,b]$ of a window $[l,r]$ simultaneously. This simultaneity is what eliminates the union bound over sketches that had cost previous sliding-window algorithms a $\\log n$ factor. The second mechanism is the Difference Estimator of [WZ22], which estimates $F_p(u+v)-F_p(v)$ additively so that StitchSW can subtract the contribution lying outside the query window; the third is a recursive randomized rounding scheme from [JW23] that compresses each sketch entry to few bits; and the fourth is a 'rotating random sets' queue that bounds the number of active timestamps without a global union bound.","core_discovery":"In the authors' own terms, the central result is Theorem 4.14: for $p\\in[1,2]$, for any fixed window $W$, with probability at least $2/3$, Algorithm 2 returns an $\\varepsilon$-approximation of $F_p^W$ using $O((\\varepsilon^{-p}\\log^2 n + \\varepsilon^{-2}\\log n\\log^4(1/\\varepsilon))(\\log(1/\\varepsilon)+(\\log\\log n)^2)) = \\tilde O(\\varepsilon^{-p}\\log^2 n+\\varepsilon^{-2}\\log n)$ bits. Theorem 1.3 complements this with a lower bound of $\\Omega(\\varepsilon^{-p}\\log^2(\\varepsilon U)+\\varepsilon^{-2}\\log(\\varepsilon^{1/p}U))$, so the algorithm is tight up to $\\log\\log n$ and $\\log(1/\\varepsilon)$ factors. The same $F_2$ estimator, combined with the heavy-hitter reduction of a prior work, yields an $O(\\varepsilon^{-p}\\log^2 n(\\log(1/\\varepsilon)+\\log\\log n))$-bit algorithm for $\\ell_p$ heavy-hitters on an arbitrary window (Theorem 1.2).","pith_inferences":["The same stitching architecture—a strong per-sub-window estimator plus difference estimators subtracted at multiple resolutions—may transfer to other sliding-window statistics that admit difference estimators, such as distinct elements or entropy-like measures, potentially carrying the same near-tight space bounds.","The lower bound works by forcing the algorithm to remember the locations of $\\Omega(\\varepsilon^{-p}\\log n)$ mini-blocks, each costing $\\log n$ bits; a plausible testable extension is whether the remaining $\\log\\log n$ and $\\log(1/\\varepsilon)$ gaps disappear under a stronger communication game or a refined rounding analysis.","The rotating-random-sets technique, which reuses independent sketch matrices through a queue to bound the number of live timestamps without a global union bound, is a general device and could reduce logarithmic factors in other histogram-based sliding-window algorithms.","If the mismatch between the $\\ell_p$-norm estimate and the $F_p$-moment estimate in StitchSW is only notational and the intended value is the $p$-th power of the sketch output, then the space analysis is unchanged but the correctness proof needs a small correction; if the mismatch is real, the $F_p$ guarantee as written would fail on simple streams."],"forward_implications":["For $1<p\\le 2$, $F_p$ moment estimation on any fixed sliding window now requires only $\\tilde O(\\varepsilon^{-p}\\log^2 n+\\varepsilon^{-2}\\log n)$ bits, matching the $\\Omega(\\varepsilon^{-p}\\log^2 n)$ lower bound up to $\\log\\log n$ and $\\log(1/\\varepsilon)$ factors.","The $\\ell_p$ heavy-hitters problem on an arbitrary window can be solved in $O(\\varepsilon^{-p}\\log^2 n(\\log(1/\\varepsilon)+\\log\\log n))$ bits, closing the $\\log n$ gap between the previous upper bound and the known lower bound.","Because the algorithm runs in the more general model where the window length $n$ is supplied at query time, the same bounds cover queries such as 'the past hour, day, or week'.","Running $O(\\log m)$ independent copies and taking a median converts the per-query $2/3$ success guarantee into a guarantee for all times, at an extra $O(\\log m)$ factor."],"supporting_citations":[{"why":"Introduces the smooth-histogram framework and the timestamp-deletion rule that keeps only O(log n) sketches; Algorithm 1 is built on it.","marker":"[BO07a]"},{"why":"Defines the Difference Estimator and its binary-tree partition structure, which Algorithm 2 adopts; also gives the prior O(ε^{-2}log^3 n) upper bound that the new result improves.","marker":"[WZ22]"},{"why":"Supplies Lemma 2.5, converting a constant-factor ℓ_2 approximation into a heavy-hitters algorithm, and the Ω(ε^{-p}log^2 n) lower bound that the heavy-hitters result matches.","marker":"[BGL+18]"},{"why":"Supplies Lemma 2.4, the tail bound on suprema of p-stable inner products over nested vectors, which is the probabilistic core of the Strong Estimator's simultaneous guarantee.","marker":"[BDN17]"},{"why":"Provides the recursive randomized rounding procedure (Lemma 4.5) used to compress Strong Estimator, p-stable sketch, and Difference Estimator entries to few bits.","marker":"[JW23]"},{"why":"Gives the general insertion-only-stream lower bound that contributes the ε^{-2}log(ε^{1/p}U) term in Theorem 1.3.","marker":"[BZ24]"},{"why":"Supplies the k-wise-independent Chernoff bound (Lemma 2.3) used in the Strong Estimator's concentration analysis.","marker":"[BR94]"},{"why":"Supplies Lemma 2.6, showing that ℓ_2 heavy hitters with a tail guarantee imply ℓ_p heavy hitters for all p∈(0,2].","marker":"[JST11]"}],"fun_headline_variants":["Sliding-window F_p estimation: tight up to log-log factors","Heavy hitters and F_p moments in sliding windows are tight","Tight bounds for sliding-window F_p moments and heavy hitters","Sliding window heavy-hitters: tight space up to small logs","F_p moment estimation in sliding windows: matching bounds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument assumes the sketch output used as the base of the stitching procedure approximates the $p$-th frequency moment $F_p$ (the sum of $p$-th powers of frequencies), while the pseudocode defines that same output as an approximation of the $\\ell_p$ norm (the $p$-th root of that sum); the proof silently switches between the two.","fun_headline_variants_meta":{"raw":{"variants":["Sliding-window F_p estimation: tight up to log-log factors","Heavy hitters and F_p moments in sliding windows are tight","Tight bounds for sliding-window F_p moments and heavy hitters","Sliding window heavy-hitters: tight space up to small logs","F_p moment estimation in sliding windows: matching bounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000932,"raw_usage":{"total_tokens":3997,"prompt_tokens":963,"completion_tokens":3034,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":579,"completion_tokens_details":{"reasoning_tokens":2944}},"tokens_in":579,"tokens_out":3034,"duration_ms":19230,"temperature":1.0,"reasoning_tokens":2944,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T05:14:51.662157+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Set $p=2$ and take the query window $W$ to contain a single distinct item once, so $F_2^W=1$. Let the stream before the window contain many copies of another item, so the suffix from the first retained timestamp has a much larger $F_2$ value. Interpret the base sketch output $X$ literally as the $\\ell_2$-norm estimate the pseudocode defines; then $Z=X-\\sum_j Y_j$ is an $\\ell_2$-norm quantity minus $F_2$-difference estimates, which will not be close to $1$. Running Algorithm 2 on this small stream and inspecting $Z$ decides whether the proof's unstated replacement of an $\\ell_2$ estimate by an $F_2$ estimate is merely notational.","supporting_citations":[],"review_version":1}