{"id":"a8272d3e-e542-4ab1-adb8-315034a541c0","arxiv_id":"2607.14432","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":2.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A survey monograph unifying the field of adversarially robust streaming: near-optimal robustness for insertion-only streams, poly(n)-space impossibility for turnstile linear sketches, and crypto-based white-box algorithms.","lead":"A survey monograph that organizes the theory of making streaming and sketching algorithms correct when the input stream adapts to the algorithm's own outputs. It maps which problems can be made robust cheaply (insertion-only streams), which provably cannot (turnstile streams under linear sketches), and how privacy and cryptography help.","discovery_kind":"review","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Chapter 7's robust turnstile F2 algorithm may be a linear sketch, which would contradict the monograph's claim that all linear-sketch turnstile algorithms need poly(n) space; the manuscript does not resolve the scope.","rationale":"I read the reader's verdict and agree that the monograph is CONDITIONAL: the positive insertion-only results are reproduced from the authors' own prior work, and Chapters 5–7 could not be fully verified from the provided text. However, I did not find the flip-number premise to be the weakest point. Within the monograph's explicitly stated insertion-only model (integer updates, polynomial bounds), Lemma 3.3.7 and Corollary 3.3.8 are standard and mathematically safe; the real-valued update case is outside the model and is flagged by the authors themselves. The more load-bearing concern is the apparent tension between Chapter 1's blanket negative statement about linear sketches in turnstile streams and Chapter 7's positive turnstile F2 result with poly(1/ε, log n) space. Either the Chapter 7 algorithm is a linear sketch, in which case the negative claim is wrong or must be restricted, or it is not a linear sketch, in which case the monograph needs to define the boundary explicitly because the abstract and introduction do not. This is an internal-consistency issue about the central claimed dichotomy, not a disagreement with prior consensus. My proposed check — reading §7.2 and comparing its state representation with the formal definition used in Chapter 5 — would settle the issue without needing to re-derive the long lower-bound proofs. Until that check is performed, CONDITIONAL remains the appropriate verdict: the monograph may well be correct, but its headline synthesis cannot be accepted as stated without resolving this scope question.","tokens_in":62412,"tokens_out":11775,"duration_ms":108354,"concrete_test":"Read §7.2 (and the technical overview §7.1.1) and determine whether the algorithm's maintained state is of the form S·x for a fixed matrix S chosen before the stream, or a fixed small number of such linear sketches. If yes, run the lower-bound attack from §5.2–§5.5 against the exact §7.2 algorithm on a small adversarially chosen turnstile stream (e.g., n=32, sketch rows t=8); if the attack succeeds, the Chapter 7 claim is false. If the algorithm instead changes its sketching matrix adaptively or uses non-linear state, verify that the formal definition of 'linear sketch' used in Chapter 5 explicitly excludes that algorithm; if it does not, the monograph must state the exclusion before the negative headline can be accepted.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The negative half of the central claim is stated in Chapter 1: 'no linear sketch based streaming algorithm for turnstile streams can be adversarially robust, that is, any such algorithm must use poly(n) memory.' But the same introduction advertises Chapter 7 as showing 'there exist streaming algorithms that are robust to adaptive adversaries while supporting both insertions and deletions,' with a concrete 'adversarially robust algorithm that achieves a (1+ε)-approximation for F2 estimation using poly(1/ε, log n) space.' If the Chapter 7 algorithm is a linear sketch — i.e., its state is a fixed linear map of the current frequency vector — then the lower bounds in Chapter 5 (e.g., §5.2–§5.5) cannot all be correct, or the term 'linear sketch based' is being used in a narrower sense than the reader would infer. Conversely, if the algorithm is not a linear sketch (for example, because its sketching matrix changes adaptively or its state is obtained by a non-linear procedure), then the negative claim needs an explicit scope restriction: the monograph currently embeds the negative result in the abstract and introduction without that caveat. Chapter 1 also says the turnstile 'saving grace' of [BEO22, WZ24] still requires memory 'polynomial in the length of the stream,' which is harder to reconcile with Chapter 7's stated poly(1/ε, log n) bound. This is not a minor terminology issue: the field's advertised landscape — robustness is nearly free on insertion-only streams and provably expensive for linear sketches on turnstile streams — is false if the Chapter 7 algorithm is itself a linear-sketch algorithm. The reader's flip-number concern is less pressing: within the stated insertion-only integer-update model, Lemma 3.3.7 is a standard monotonicity argument and appears sound.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This monograph surveys and systematizes recent work on adversarial robustness of streaming and sketching algorithms. It develops the black-box insertion-only model, proving robustness of Bernoulli and reservoir sampling (Lemmas 3.1.5–3.1.8), an attack on the AMS sketch (Thm. 3.2.1), and generic frameworks—sketch switching (Thm. 3.3.4), bounded computation paths (Thm. 3.4.1), and difference estimators (Thm. 3.5.5, Algorithm 6)—that convert oblivious strong trackers into adversarially robust algorithms for F2, Fp, and F0 estimation with near-optimal space. It also discusses connections to differential privacy, white-box cryptography, and lower bounds for linear sketches in turnstile streams, and announces in Chapter 7 an adversarially robust F2 estimation algorithm for turnstile streams in poly(1/ε, log n) space for functions satisfying an approximate triangle inequality.","tokens_in":62588,"tokens_out":12562,"duration_ms":112041,"significance":"If the result holds, this is a valuable synthesis: it brings together the main positive techniques of [BJWY22, WZ21b] and the main negative results for linear sketches, with self-contained proofs in the reviewed portions. The flip-number premise is explicit and proved (Lemma 3.3.7, Cor. 3.3.8), and the F2 difference-estimator chain (Lemmas 3.5.6–3.5.11, Thm. 3.5.12) is structurally sound and free of fitted parameters or circular reductions. The value of the monograph depends critically on the precise scoping of the turnstile results, and the current text does not state that scope sharply enough. With that fixed, the monograph would be a useful reference for the field.","major_comments":[{"comment":"The headline negative claim in §1 is that 'no linear sketch based streaming algorithm for turnstile streams can be adversarially robust, that is, any such algorithm must use poly(n) memory'. The same introduction advertises Chapter 7 as giving a robust F2 algorithm in turnstile streams using poly(1/ε, log n) space. The manuscript never states whether the Chapter 7 algorithm is a linear sketch, nor does it define the precise class of algorithms to which the lower bound applies (e.g., fixed data-independent sketching matrix versus adaptively chosen matrices). §1 also says the DP-based 'saving grace' of [BEO22, WZ24] still requires memory polynomial in the stream length, which is hard to reconcile with the poly(1/ε, log n) claim for Chapter 7. This is load-bearing for the monograph's advertised landscape; the authors should either restrict the lower bound to fixed-matrix linear sketches and","section":"Ch. 1 and announced Ch. 7 (§1.4)"},{"comment":"The proof of the lower-bound half of Lemma 3.5.3 is incomplete. After the sentence beginning 'Moreover by the correctness of A, we have F(1,t′_{c,z_i})−F(1,t′_{c,z_i+1})≤F(1,t) since A_c(1,t_c,η,δ)' the text stops and the inequality chain is not finished. This lemma is used in Theorem 3.5.5 to control the number and accuracy of the difference estimators, so the omitted derivation is not merely cosmetic. Please supply the complete argument.","section":"§3.5.1, Lemma 3.5.3"},{"comment":"The proof of Lemma 3.5.2 contains the garbled statement 'for c to increase, the output of A_i has to be at least 2c'. Here c is a counter, not a value, so the sentence as written is not meaningful; it presumably means at least twice the previous active estimate. The next sentence claims that F must have increased by at least 3/2, but the derivation is not shown. Since this lemma underlies the bound on the number of times the framework switches the active sketch, it should be stated precisely.","section":"§3.5.1, Lemma 3.5.2"}],"minor_comments":[{"comment":"The sentence 'if the stream has a large number of +1/-1 updates, then the Euclidean norm and other common statistics take too long to change by a large amount' is difficult to parse and appears to be in tension with the earlier observation that in turnstile streams the approximate function value can change poly(n) times. Please rewrite and clarify the intended regime.","section":"§1"},{"comment":"The proof refers to quantities S1(n,δ′,ε) and S2(n,δ′,ε) without defining them in the theorem statement. This makes the space bound hard to verify.","section":"§3.5.2, Thm. 3.5.13"},{"comment":"The induction in Claim 3.1.10 uses the expression ℓ_i ≥ p′^{|S|}(1−2p′)^{n−|S|}·N, but the exponent of (1−2p′) is not clearly derived from the update rule. Please spell out the induction step.","section":"§3.1.1.3, Claim 3.1.10"},{"comment":"The statement 'E[s_i s_j s_k s_l] = 1 if i,j,k,l consists of two (possibly not distinct) pairs' is terse. Please identify the three possible two-pair matchings explicitly, since the factor 2 in the variance bound depends on that count.","section":"§3.5.2, Lemma 3.5.7"}],"recommendation":"major_revision","confidential_remarks":"The main risk to the monograph is the unresolved scope of the turnstile lower bound relative to the announced Chapter 7 upper bound. If the Chapter 7 algorithm is a fixed linear sketch, the internal contradiction is serious; if it is not, the authors need to say so explicitly in the abstract and introduction. I was unable to verify the Chapter 5–7 content from the provided excerpt, so my confidence is concentrated on the positive insertion-only chapters, which are sound in the parts I checked. The monograph is largely a synthesis of prior work; the editors may wish to check that the novelty and attribution relative to [BJWY22] and [WZ21b] are clearly stated."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Punchline: this is a survey monograph, not a new-results paper. Its contribution is organizational: a single notation, a clear black-box/white-box and insertion-only/turnstile hierarchy, and a coherent narrative that makes roughly a decade of results (BJWY22, WZ21b, HKM+22, BEO22/WZ24, ABJ+22) tractable. The parts I could actually read—introduction, Chapter 2, and Chapter 3 through §3.5.2—are honest about provenance: theorems are attributed to prior work, and the reproduced proofs, including the martingale analyses for Bernoulli and reservoir sampling, the AMS attack, sketch switching, bounded computation paths, and the F2 difference estimator, are structurally sound. No free parameters, no fitting, no definitional circularity. That is a real service, and for a Foundations and Trends volume it is enough.\n\nWhere I would push back: first, the load-bearing positive results (sketch switching, bounded computation paths, difference estimators) come from the authors' own prior papers, reproduced rather than independently verified. That is normal for a monograph by the principals, and the proofs shown match the literature, but it means a skeptical reader still has to trust [BJWY22, WZ21b, WZ24] for the parts not in the text. Second, I cannot verify Chapters 4–7 from what was provided; the turnstile lower-bound story, the white-box chapter, and the claimed Chapter 7 algorithm are present only as a table of contents and preview sentences. The stress-test worry about Chapter 7 versus the linear-sketch lower bounds is therefore not decidable from this submission. The negative claim in Chapter 1 is explicitly scoped to \"linear sketch based\" algorithms, so there is no flat contradiction visible; but the monograph should state in the introduction whether the Chapter 7 F2 algorithm is a linear sketch. If it is, the lower bounds need a narrower scope; if it is not, say so and stop readers from tripping on the juxtaposition. Third, minor hygiene: the §1.3.1 attack uses the midpoint, while Algorithm 2 uses the (1−p′) quantile; Lemma 3.1.26 says C > κ^p but Algorithm 3 sets α = C d/ε² log(nκ) with C > κ². Cosmetic, but worth cleaning.\n\nThe flip-number concern raised by the reader does not bother me. Lemma 3.3.7 is a standard monotonicity argument and is correct in the stated integer-update insertion-only model; the manuscript's own turnstile contrast is exactly the right caveat.\n\nBottom line: this deserves a serious referee. The right referee should have the full chapters and should specifically check that the Chapter 7 algorithm's relationship to linear sketches is stated correctly. I would be happy to cite the monograph as a reference for the black-box model and the F2 difference-estimator framework.","headline":"Honest, well-organized survey monograph, not a new-results paper; the unified treatment is genuinely useful, but the intro's turnstile claims need one clarifying sentence about whether Chapter 7's algorithm is a linear sketch.","tokens_in":63439,"tokens_out":4461,"would_cite":true,"duration_ms":48005,"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":"This monograph establishes the cost of adaptive robustness in streaming: insertion-only streams admit near-optimal robust estimators, while turnstile linear sketches provably require polynomial memory.","keywords":["adversarial robustness","streaming algorithms","linear sketches","flip number","difference estimators","frequency moments","insertion-only streams","turnstile streams"],"falsifier":"Construct an insertion-only stream of length poly(n) with integer updates in which the F2 moment undergoes more than c·eps^{-1} log n multiplicative (1±eps) changes; this would falsify the flip-number bound (Lemma 3.3.7 / Corollary 3.3.8) on which all near-optimal positive results rest. Alternatively, exhibit a linear sketch for turnstile streams that is adversarially robust for F2 using polylog(n) memory, which would contradict the paper's lower bound.","tokens_in":62079,"feed_emoji":"🛡️","tokens_out":5933,"duration_ms":59924,"temperature":0.7,"pith_summary":"Adaptive inputs break classical streaming guarantees, and the paper asks what it costs to make streaming algorithms correct when the stream depends on past outputs. The central finding is a sharp split: on insertion-only streams, adversarially robust algorithms for the F2 moment and related statistics match the space of their non-robust counterparts up to logarithmic factors, using frameworks built on the flip number of the statistic. On turnstile streams with deletions, any linear sketch must use polynomial memory to be adversarially robust, so robustness is provably expensive; a saving grace is a robust algorithm for functions with an approximate triangle inequality, achieving (1+eps)-F2 estimation in poly(1/eps, log n) space. The monograph also shows differential privacy can hide internal randomness, and that cryptographic hardness assumptions yield robustness against white-box adversaries.","feed_headline":"Robust streaming costs almost nothing on insertion-only streams","feed_subtitle":"F2 estimation resists adaptive inputs in near-optimal space, while deletions force linear sketches to polynomial memory.","key_machinery":"The flip number — the maximum number of times a monotone statistic changes by a (1±eps) factor — is the load-bearing quantity. For insertion-only streams with integer updates, it is bounded by O(eps^{-1} log n) because a non-zero integer moment is at least 1 and at most n^{O(1)}. The frameworks exploit this: sketch switching runs a fresh independent sketch at each flip; bounded computation paths union-bound over all possible output sequences; difference estimators (with sketch stitching) estimate only the increments between flips, reducing the overhead to near-optimal. For turnstile streams the flip number can be polynomial, which is why the lower bounds hold; the saving grace comes from an","core_discovery":"The monograph's synthesis is two-sided. Positively, there exist adversarially robust insertion-only streaming algorithms that output a (1+eps)-approximation to the F2 moment at all times using O-tilde(1/eps^2 log n) bits, matching optimal non-adaptive algorithms up to logarithmic factors; similar near-optimal robust algorithms hold for Fp (0