{"id":"92b499c0-6ca6-455e-809b-db2e94ccfbdf","arxiv_id":"2412.05807","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Improved adversarially robust Lp heavy hitters and Lp estimation on turnstile streams, with a small asymptotic space improvement over the prior dense-sparse tradeoff.","lead":"This paper gives smaller-memory algorithms for tracking heavy items and total size in data streams where an adversary can adapt to the algorithm's previous answers. The improvement is modest, but it shows the earlier dense-sparse method was not a fundamental barrier.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 3's residual estimate has a dimensionally wrong scaling: the output sums T_ℓ(1+η)^{2ℓ}, while Definition 3.1 implies each level-ℓ item contributes ≈ζM/(1+η)^ℓ. Lemma 3.5's error bound is therefore inconsistent, so Theorem 3.6 and the main theorem are not established.","rationale":"The reader identified DetHH's universe parameter as the weakest assumption, but the most direct obstruction to Theorem 1.3 is the scaling error in Algorithm 3. Even if DetHH were run on a universe of size t via hashing or dictionary compression, the DENSE branch of Algorithm 4 would still rely on ResidualEst, whose output is not a valid estimate of F_{p,Res}(k) under the paper's own definitions. The proof of Lemma 3.5 contains the same inconsistency: it defines \\hat Dℓ with a (1+η)^ℓ factor where the definition of Dℓ demands a ζM/(1+η)^ℓ factor. Because M is never used in the algorithm's output, the error cannot be dismissed as a minor constant factor; it grows rapidly in ℓ. I therefore keep the reader's CONDITIONAL verdict: the approach is promising and likely repairable, but the current manuscript does not establish Theorem 1.3. The DetHH issue should also be addressed, but it is secondary to the residual-estimation bug.","tokens_in":22697,"tokens_out":16424,"duration_ms":149915,"concrete_test":"Run a small simulation of Algorithm 3 on a fixed vector, e.g., n=1000, p=2, m=100, ε=0.1, with ten coordinates of value 10 and one hundred coordinates of value 1, k=5. Compute the returned ∑_ℓ Tℓ(1+η)^{2ℓ} and compare with F_2,Res(5); the per-level error will be off by roughly (1+η)^{3ℓ}/(ζM). More directly, re-derive the inequality in Lemma 3.5 after substituting Dℓ = |Λℓ|ζM/(1+η)^ℓ and \\hat Dℓ = |Λℓ|(1+η)^ℓ; the claimed bound fails unless ζM=(1+η)^{2ℓ}, which is impossible for all ℓ. This settles that Theorem 3.6 does not follow from the presented algorithm.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Algorithm 3 (lines 13–16) sets \\hat|Λℓ| = Tℓ·(1+η)^ℓ and returns ∑_ℓ \\hat|Λℓ|(1+η)^ℓ = ∑_ℓ Tℓ(1+η)^{2ℓ}. Under Definition 3.1, a level-ℓ item has (f_j)^p ∈ [ζM/(1+η)^{ℓ-1}, ζM/(1+η)^ℓ), so its p-th moment contribution is ≈ζM/(1+η)^ℓ. The algorithm's output therefore differs from the correct level contribution by a factor of roughly (1+η)^{3ℓ}/(ζM), which is unbounded as ℓ grows; the parameter M never appears in the output. Lemma 3.5's proof explicitly asserts \\hat Dℓ = |Λℓ|(1+η)^ℓ and claims |\\hat Dℓ−Dℓ| ≤ η(1+η)Cℓ. Substituting Dℓ ≈ |Λℓ|ζM/(1+η)^ℓ shows the claimed inequality would require ζM = (1+η)^{2ℓ} for all ℓ, which is false for fixed M ≈ m^p and varying ℓ. Consequently Theorem 3.6 is unsupported, and since Algorithm 4 relies on ResidualEst in the DENSE case (lines 14–16), the correctness chain behind Theorem 1.3 fails. This is an internal inconsistency in the pseudocode and proof, not a matter of external consensus. The DetHH universe issue raised by the reader is real, but repairing it alone would not restore Theorem 1.3.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies adversarially robust Lp estimation in the turnstile streaming model and proposes an improved dense-sparse trade-off. It introduces (i) an adversarially robust Lp-heavy-hitter algorithm that combines a deterministic heavy-hitter algorithm (DetHH) for small-support states with a robust CountSketch for dense states, and (ii) a residual-estimation algorithm that estimates the p-th moment of the tail vector via subsampling and level-set counting. These are combined in a dense-sparse framework to obtain an O~(m^c) space algorithm for (1+epsilon)-approximate Lp estimation at all times for p in [1,2] with c = (24p^2-23p+4)/((4p-3)(12p+3)), claimed to be an improvement over the previous trade-off of Ben-Eliezer, Eden, and Onak for p in (1,2).","tokens_in":22985,"tokens_out":12943,"duration_ms":111695,"significance":"If the claims were correct, this would be the first asymptotic improvement over the BEO22 dense-sparse trade-off for p in (1,2), showing that the previous framework is not an inherent barrier. The proposed residual-estimation subroutine with space independent of the tail parameter k is also a potentially reusable component, and the paper is clearly written with a useful technical overview. The empirical evaluation and public code are welcome. However, two load-bearing components currently have serious gaps: the application of DetHH to a large universe is unjustified, and the residual-estimation algorithm's output formula is inconsistent with its own definitions. These issues prevent the main theorems from being established as written.","major_comments":[{"comment":"","section":"§2 (Algorithm 2, Lemma 2.7)"},{"comment":"","section":"§3 (Algorithm 3, lines 13–16; Lemma 3.5)"},{"comment":"","section":"§3 (Lemma 3.5)"}],"minor_comments":[{"comment":"The interval in Definition 3.1 is written for f_i, but Algorithm 3 and Lemma 3.5 use intervals for (f_j)^p. Please make the definition consistent, e.g., define Γ_ℓ via (f_i)^p.","section":"Definition 3.1"},{"comment":"The variable i in 'Let M = 2^i' is reused from the loop index in lines 2–6; this is confusing and should be renamed.","section":"Algorithm 3, line 7"},{"comment":"The proof contains an incomplete sentence: 'We that we achieve a (1+O~(ε))-approximation...'.","section":"Lemma 3.5"},{"comment":"The statement 'because the number of distinct elements is at least 50t, then we have ∥f∥_p ≥ 50 t^{1/p}' is not mathematically correct; it should be ∥f∥_p ≥ (50t)^{1/p}. The conclusion of the argument still follows with adjusted constants, but the inaccurate inequality should be corrected.","section":"Lemma 2.5"},{"comment":"The empirical section reports flip-number ratios rather than the actual space usage of the proposed algorithm versus BEO22; this is acceptable for a proof of concept but should be described as such, and the claim 'significantly less space' should be confined to the flip-number proxy.","section":"§5 (Empirical Evaluations)"}],"recommendation":"major_revision","confidential_remarks":"The paper contains promising ideas, but the two main components have substantial correctness gaps. The residual-estimation scaling error appears to be a genuine bug in both the pseudocode and the proof, not just a typo, though it may be repairable. The DetHH universe issue also requires a substantive fix or a modification of the algorithm. I recommend major revision with a careful rewrite of Section 3 and a justification or adjustment of Section 2. The authors should also double-check the randomized ζ argument."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe main theorem rests on a residual estimation subroutine that doesn't work as written. Algorithm 3 counts items in each level set, subtracts the heavy tail, and returns sum of T_ell * (1+eta)^(2ell). Under Definition 3.1 as used in the proofs, an item in level ell contributes about zeta*M/(1+eta)^ell to the p-th moment, so the output should scale with M/(1+eta)^ell, not (1+eta)^ell. The parameter M never appears in the output, and Lemma 3.5's error bound is dimensionally inconsistent with the definition of D_ell. This is not a minor gap; it is the load-bearing step behind Theorem 1.3.\n\nThere is real value here. Theorem 1.2's robust heavy-hitter exponent (2p-2)/(4p-3) improves over the dense-sparse p/(2p+1) for p in [1,2), and the idea of estimating the tail's p-th moment in space independent of the tail parameter k is the right goal. The deterministic heavy-hitter plus robust CountSketch combination is coherent, and the differential-privacy framework is standard. The experiments are rightly labeled proof-of-concept.\n\nThe DetHH universe issue the reader flagged is also real: Algorithm 2 runs DetHH with a universe parameter t while Theorem 2.1's space bound depends on the ambient universe size, and no universe reduction is given. That gap looks repairable with a dictionary or hash-based reduction, but it is unstated.\n\nIf the scaling bug is fixed, the paper could be an interesting step forward. As written, Theorem 1.3 is not established. The heavy-hitter portion deserves a serious referee, and the residual idea is salvageable, but the authors need to correct the pseudocode and re-prove Lemma 3.5 before the main claim can be credited.\n\nRecommendation: send to peer review with a note that the residual subroutine needs careful re-examination, but do not accept the current version.","headline":"The heavy-hitter result is a real step, but the residual estimation subroutine has a scaling bug that breaks Theorem 1.3.","tokens_in":23562,"tokens_out":6075,"would_cite":false,"duration_ms":54081,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W27","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that adversarially robust Lp norm estimation on turnstile streams can be done in $\\tilde{O}(m^c)$ space for $c<\\frac{p}{2p+1}$, the first improvement over the dense-sparse framework for all $p\\in(1,2)$.","keywords":["adversarial streaming","turnstile streams","Lp norm estimation","heavy hitters","dense-sparse tradeoffs","differential privacy","residual estimation","frequency moments"],"falsifier":"A decisive check is to instantiate Algorithm 2 with $t$ much smaller than $n$, then feed it a stream whose updates touch only coordinates outside the assumed $t$-sized universe; if DetHH cannot represent or process those coordinates within its stated $\\tilde{O}(t^{2-2/p})$ bits, then either the space bound or the all-times heavy-hitter guarantee must fail. A more quantitative version is to compute, for $p=1.5$, the actual space of DetHH on a universe of size $n\\gg m^{p/(4p-3)}$ and compare it with the claimed $\\tilde{O}(m^{(2p-2)/(4p-3)})$ bound.","tokens_in":22393,"feed_emoji":"📊","tokens_out":5085,"duration_ms":49566,"temperature":0.7,"pith_summary":"This paper answers an open question by showing that the dense-sparse tradeoff of Ben-Eliezer, Eden, and Onak is not a fundamental barrier for adversarially robust Lp estimation on turnstile streams. Its strategy is to track Lp heavy hitters deterministically when the active universe is small and with a differentially private CountSketch ensemble when the universe is large, then to estimate the tail of the frequency vector with a new oblivious subroutine whose space is independent of the tail size. The headline result, Theorem 1.3, achieves $\\tilde{O}(m^c)$ space for the exponent $c=\\frac{24p^2-23p+4}{(4p-3)(12p+3)}$, which beats the previous $p/(2p+1)$ exponent for every $p\\in(1,2)$.","feed_headline":"First streaming Lp gain past dense-sparse tradeoff","feed_subtitle":"Tracking heavy hitters shrinks the flip number, beating the old m^{p/(2p+1)} space bound for p in (1,2).","key_machinery":"The load-bearing object is a pair of heavy-hitter subroutines: DetHH, a deterministic turnstile heavy-hitter algorithm whose space grows like $\\tilde{O}(t^{2-2/p})$ in the size $t$ of the universe it is instantiated on, and RobustCS, an adaptively robust version of CountSketch. Algorithm 2 switches between the two based on an L0 estimate from LZeroEst, using DetHH when the active coordinate count is at most $O(t)$ and RobustCS otherwise. The residual estimator ResidualEst then partitions coordinates into level sets by magnitude, subsamples the universe, finds heavy items in each subsampled level set, rescales their counts, and subtracts the top $k$ coordinates, which is why its space does not depend on $k$. Balancing the sparse-recovery sparsity, the heavy-hitter threshold, and the number of differential-privacy instances sets the final exponent $c$.","core_discovery":"The central discovery is that the hard regime for the previous framework, where the frequency vector has many nonzero entries, is actually easier than its flip-number analysis suggests: a long sequence of updates can change the p-th moment of the residual vector only if most updates land on coordinates that are or become heavy hitters. By maintaining an adversarially robust heavy-hitter data structure, the paper forces the adversary to spread updates across many coordinates before the residual moment changes, which lowers the number of independent sketch instances needed. Combined with a new residual-estimation algorithm that approximates the p-th moment of the tail up to additive $\\varepsilon$ error in space polynomial in $1/\\varepsilon$ and $\\log n$, this yields the improved space exponent of Theorem 1.3. The paper further proves a standalone robust heavy-hitter theorem, Theorem 1.2, with space $\\tilde{O}(\\varepsilon^{-2.5} m^{(2p-2)/(4p-3)})$.","pith_inferences":["Editorial inference: the same heavy-hitter-first reduction likely applies to other statistics on turnstile streams, such as symmetric norm estimation or cascaded norm estimation, wherever the residual flip number is smaller than the full flip number.","Editorial inference: if DetHH were replaced by a deterministic sketch with milder dependence on the ambient universe size, the exponent in Theorem 1.3 could improve further; the paper's own balancing choices appear to be artifacts of DetHH's universe dependence.","Editorial inference: the level-set subsampling estimator may have standalone uses in differentially private streaming, since it gives tail estimation with space independent of the tail parameter and only additive accuracy loss.","Editorial inference: the empirical flip-number comparison on the CAIDA dataset suggests a testable prediction, namely that on real traffic data the residual flip number is consistently 1.1 to 1.75 times smaller than the full flip number across accuracy settings."],"forward_implications":["If Theorem 1.3 is correct, adversarially robust Lp estimation on turnstile streams has space complexity strictly below the dense-sparse tradeoff for all $p\\in(1,2)$, breaking the equality that previously held at $p/(2p+1)$.","The robust heavy-hitter result of Theorem 1.2 gives space $\\tilde{O}(m^{(2p-2)/(4p-3)})$ for all $p\\in[1,2)$, which is polylogarithmic at $p=1$ and improves the dense-sparse heavy-hitter analog for every $p<2$.","The residual-estimation subroutine of Theorem 3.6 estimates the p-th moment of a tail vector omitting the top $k$ coordinates using space independent of $k$, up to additive $\\varepsilon$ error measured against a slightly shorter tail.","Taken together, the results show that the dense-sparse tradeoff is a technique-dependent bound rather than an information-theoretic impossibility for these problems."],"supporting_citations":[{"why":"Supplies the dense-sparse tradeoff framework and the flip-number argument that this paper improves on.","marker":"[BEO22]"},{"why":"Provides the deterministic turnstile heavy-hitter algorithm DetHH whose space bound is the key tradeoff in the robust heavy-hitter construction.","marker":"[GM07]"},{"why":"Gives CountSketch, the heavy-hitter subroutine used in the robust dense case and in the residual level-set estimation.","marker":"[CCF04]"},{"why":"Establishes the differential-privacy framework that converts oblivious streaming algorithms into algorithms robust to adaptive queries with roughly square-root flip-number overhead.","marker":"[HKM+20]"},{"why":"Extends the differential-privacy framework and is used for the robust L0 estimation and residual estimation instance counts.","marker":"[ACSS23]"},{"why":"Gives RobustCS, the adaptively robust CountSketch used for the dense-universe case in Algorithm 2.","marker":"[CLN+22]"},{"why":"Introduces the subsampling framework for estimating frequency moments that the residual estimation algorithm builds on.","marker":"[IW05]"},{"why":"Provides the LZeroEst distinct-elements estimator used to decide between the sparse and dense states.","marker":"[KNW10]"},{"why":"Supplies the deterministic sparse-recovery algorithm used to output the full vector when the stream is declared sparse.","marker":"[GSTV07]"}],"fun_headline_variants":["Heavy hitters unlock robust Lp streaming breakthrough","Adversarial streaming Lp: heavy-hitter route slashes space","Lp estimation defies dense-sparse limit with heavy hitters","Heavy-hitter twist beats old streaming Lp bounds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The main theorem assumes that the deterministic heavy-hitter algorithm DetHH can be run on a universe of size $t=O(m^{p/(4p-3)})$ while the stream's coordinates come from the full universe $[n]$, with $n$ potentially much larger than $t$; the paper gives no dictionary or hash-based reduction that would let DetHH ignore coordinates outside its declared universe, and DetHH's space bound grows with the universe size it is instantiated on.","fun_headline_variants_meta":{"raw":{"variants":["Heavy hitters unlock robust Lp streaming breakthrough","Adversarial streaming Lp: heavy-hitter route slashes space","Lp estimation defies dense-sparse limit with heavy hitters","Heavy-hitter twist beats old streaming Lp bounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000252,"raw_usage":{"total_tokens":1556,"prompt_tokens":939,"completion_tokens":617,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":555,"completion_tokens_details":{"reasoning_tokens":546}},"tokens_in":555,"tokens_out":617,"duration_ms":6373,"temperature":1.0,"reasoning_tokens":546,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T20:22:59.213955+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A decisive check is to instantiate Algorithm 2 with $t$ much smaller than $n$, then feed it a stream whose updates touch only coordinates outside the assumed $t$-sized universe; if DetHH cannot represent or process those coordinates within its stated $\\tilde{O}(t^{2-2/p})$ bits, then either the space bound or the all-times heavy-hitter guarantee must fail. A more quantitative version is to compute, for $p=1.5$, the actual space of DetHH on a universe of size $n\\gg m^{p/(4p-3)}$ and compare it with the claimed $\\tilde{O}(m^{(2p-2)/(4p-3)})$ bound.","supporting_citations":[],"review_version":1}