Pith. sign in

REVIEW 3 major objections 4 minor 20 references

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.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-02 02:07 UTC pith:Q4TFFGW4

load-bearing objection 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. the 3 major comments →

arxiv 2607.14432 v1 pith:Q4TFFGW4 submitted 2026-07-15 cs.DS

The Adversarial Robustness of Sketching and Streaming Algorithms

David P. Woodruff , Samson Zhou This is my paper
classification cs.DS
keywords adversarial robustnessstreaming algorithmslinear sketchesflip numberdifference estimatorsfrequency momentsinsertion-only streamsturnstile streams
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

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.

Core claim

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<p<2) and F0. Negatively, no linear sketch based streaming algorithm for turnstile streams can be adversarially robust — any such algorithm must use poly(n) memory — unless the statistic satisfies an approximate triangle inequality, in which case a robust algorithm achieves (1+eps)-F2 estimation in poly(1/eps, log n) space. The monograph further shows tha

What carries the argument

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

Load-bearing premise

The flip-number premise: in an insertion-only stream with integer updates bounded by poly(n), a monotone statistic like F2 changes by a (1±eps) factor at most O(eps^{-1} log n) times; if this bound fails (e.g., with real-valued updates or sub-1 weights), the near-optimal robust algorithms stop working.

What would settle it

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.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Adversarially robust F2 estimation on insertion-only streams uses O-tilde(1/eps^2 log n) bits, the same order as classical non-robust sketches, so adaptivity is nearly free for this problem.
  • Linear sketches for turnstile streams require polynomial memory to be adversarially robust; hence robustness, not just accuracy, is the bottleneck in the presence of deletions.
  • For functions satisfying an approximate triangle inequality, robust turnstile algorithms exist with poly(1/eps, log n) space, giving a class of problems that escape the lower bound.
  • The flip-number frameworks give generic black-box transformations: any strong tracker with space S becomes an adversarially robust algorithm with space O(S · lambda), where lambda is the flip number.
  • Differential privacy can be used to hide a sketch's internal randomness, yielding a quadratic improvement over flip-number-based approaches in some regimes, and extending robustness to adaptive data analysis.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The flip-number principle suggests a design heuristic beyond the paper's examples: any monotone statistic whose value is polynomially bounded and changes multiplicatively slowly can likely be made adaptively robust at essentially no extra cost; the hard regime is non-monotone statistics.
  • The turnstile lower bounds target linear sketches; the paper leaves open whether non-linear sketches could provide subpolynomial-space robustness, a natural next question given that many turnstile algorithms are linear by design.
  • The difference-estimator construction may transfer to other adaptive settings, such as sliding windows or interactive optimization, where only increments of the target function are needed between adaptive queries.
  • If fractional or real-valued updates were allowed on insertion-only streams, the flip-number bound would fail and the near-optimal positive results would collapse; this identifies a boundary of the model worth testing in practice.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 4 minor

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.

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 (3)
  1. [Ch. 1 and announced Ch. 7 (§1.4)] 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
  2. [§3.5.1, Lemma 3.5.3] 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.
  3. [§3.5.1, Lemma 3.5.2] 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.
minor comments (4)
  1. [§1] 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.
  2. [§3.5.2, Thm. 3.5.13] 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.
  3. [§3.1.1.3, Claim 3.1.10] 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.
  4. [§3.5.2, Lemma 3.5.7] 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.

Circularity Check

0 steps flagged

No circularity found: the positive robust-F2/Fp results are derived in-text from the flip-number premise plus explicit difference-estimator constructions, and the turnstile lower bounds are presented as self-contained attack proofs rather than imported conclusions.

full rationale

Every load-bearing positive claim is derived rather than assumed. Lemma 3.3.7 and Corollary 3.3.8 bound flip numbers from monotonicity, integrality, and the poly(n) magnitude bound. The sketch-switching and bounded-computation-path frameworks (Theorems 3.3.4 and 3.4.1) are proved by explicit union-bound and computation-path arguments. Theorem 3.5.5 reduces robust insertion-only estimation to a strong tracker plus a difference estimator, and Sections 3.5.2-3.5.4 construct those primitives from AMS-style and p-stable sketches with explicit expectation, variance, and chaining proofs. No parameter is fitted to the target quantity, and no output is statistically forced by a fit. The WZ21b and BJWY22 citations are attributions for frameworks whose proofs are reproduced in the monograph itself, so they are not load-bearing self-citations in the circularity sense. The turnstile negative results are supported in Chapter 5 by explicit adaptive-reconstruction attacks, not merely by the citation in Chapter 1. I noted an internal tension between Chapter 1's statement that the BEO22/WZ24 turnstile saving grace still requires memory polynomial in the stream length and Chapter 7's advertised poly(1/epsilon, log n) space, but that is a consistency/scoping concern, not a circular reduction, so it does not raise the circularity score.

Axiom & Free-Parameter Ledger

0 free parameters · 8 axioms · 0 invented entities

The ledger lists the background facts the surveyed results rest on. There are no fitted free parameters anywhere in the reviewed portion — all constants (C, α, δ, η, γ_j, p′) are analysis parameters, and the surveyed algorithms deliberately replace union-bound-over-time parameters with flip-number/flip-count parameters as a matter of theory. The two load-bearing domain assumptions are the flip-number premise (insertion-only, poly-bounded integer updates) and the linear-sketch restriction for turnstile lower bounds; SIS and the derandomization lemma enter only in specific chapters. Everything else is standard probability/analysis background reproduced in Ch. 2. No new entities are postulated: the adversarial models (black-box, white-box) and the difference-estimator primitive are definitions of frameworks from the cited literature ([BJWY22], [WZ21b]), reproduced with attribution, not new objects introduced by this monograph.

axioms (8)
  • standard math Standard probability tools: Chernoff bounds, Khintchine's inequality, martingale concentration (Freedman; [CL06] Thm 6.1 with variance and step-size bounds)
    Used throughout Ch. 3 for the robust-sampling proofs (Lemmas 3.1.4–3.1.8, Thm 3.1.25) and the AMS attack (Thm 3.2.1).
  • standard math p-stable distributions exist for all p ∈ (0,2] (Zol89) and can be sampled (Nol03)
    Basis of the Fp difference estimator (§3.5.3, Def. 3.5.17, Thm 3.5.18); the geometric-mean estimator of [Li08] requires p-stable entries.
  • standard math Discrete Gaussian normalization bound (Fact 2.1.3, [CKS20])
    Used in Lemma 2.1.4 to relate discrete and truncated-continuous Gaussians — background for Ch. 5's lattice arguments.
  • standard math Without loss of generality the adaptive adversary is deterministic (averaging over its random bits)
    Invoked in Thm 3.3.4 and Thm 3.4.1 to make the adversarial stream a fixed function of the algorithm's outputs.
  • domain assumption Insertion-only streams with integer updates bounded by poly(n): non-zero Fp moments lie in [1, n^{O(1)}], so the ε-flip number is O(ε^{-1} log n)
    Load-bearing for every near-optimal positive result (Lemmas 3.3.7–3.3.8; sketch switching, bounded paths, difference estimators). Fails for real-valued updates, sub-unit weights, or turnstile streams — the survey itself flags the turnstile failure in §1.
  • domain assumption Turnstile lower bounds are established against linear sketches, which the survey asserts (citing [LNW14, AHLW16]) are essentially optimal for non-robust turnstile problems
    The impossibility narrative (Ch. 5; 'no linear sketch based streaming algorithm for turnstile streams can be adversarially robust') is a statement about linear sketches; its force as a general lower bound inherits the linear-sketches-are-optimal thesis from the cited literature.
  • domain assumption SIS (Short Integer Solution) cryptographic hardness for computationally bounded white-box adversaries
    Ch. 6 upper bounds (sparse/low-rank/tensor recovery, vector recovery) rely on SIS; noted in §1.4 and the Ch. 6 overview. Proofs not visible in the reviewed portion.
  • domain assumption Pseudorandom derandomization of linear sketches (JW18 Lemma 8, generalized in Cor. 3.5.27) preserves marginal distributions up to n^{-ck}
    Needed to convert p-stable difference estimators into O(k log n (log log n)^2)-bit implementations; the generalization packs q sketches into one vector with a unique N^2-ary decoding (§3.5.3).

pith-pipeline@v1.3.0-alltime-deepseek · 61605 in / 28794 out tokens · 244762 ms · 2026-08-02T02:07:06.893151+00:00 · methodology

0 comments
read the original abstract

Sketching and streaming algorithms are vital for handling massive datasets. While classical methods guarantee correctness on fixed inputs, they often fail with adaptive inputs, where future data depends on past algorithm outputs. This is common in settings such as optimization, databases, finance, and network monitoring. This monograph surveys recent advances in adversarial robustness, including techniques for insertion-only streams, connections to differential privacy, and cryptographic methods that achieve adversarial robustness. We also discuss fundamental limitations, especially for linear sketches and streams with insertions and deletions, where robustness often requires polynomial space or sketching dimension. Throughout, we explore core problems like adaptively answering queries for optimization problems, norm estimation, frequency moments, and heavy hitters, and highlight emerging tools and open challenges at the intersection of streaming, sketching, privacy, and adversarial robustness.

Figures

Figures reproduced from arXiv: 2607.14432 by David P. Woodruff, Samson Zhou.

Figure 3
Figure 3. Figure 3 [PITH_FULL_IMAGE:figures/full_fig_p057_3.png] view at source ↗
Figure 3.1
Figure 3.1. Figure 3.1: Example of possible computation paths by adversary to union bound for correctness. Each [PITH_FULL_IMAGE:figures/full_fig_p058_3_1.png] view at source ↗
Figure 3.2
Figure 3.2. Figure 3.2: Difference estimator outputs (in blue) are stitched together with streaming algorithm [PITH_FULL_IMAGE:figures/full_fig_p061_3_2.png] view at source ↗
Figure 3
Figure 3. Figure 3 [PITH_FULL_IMAGE:figures/full_fig_p062_3.png] view at source ↗
Figure 3.3
Figure 3.3. Figure 3.3: Difference estimator for Fp(u + v) − Fp(u) with 0 < p < 2 expand zi −z ′ i as a sum of 2 q −1 geometric means of q terms, each with at least one term |⟨Aj , v⟩|p/q . Since Aj is a vector consisting of independent p-stable random variables, then (⟨Aj , v⟩) p/q has the same distribution as (∥v∥p · X) p/q for a p-stable random variable X. Hence, if Fp(v) ≤ γ · Fp(u), then we can upper bound the probability … view at source ↗
Figure 3
Figure 3. Figure 3 [PITH_FULL_IMAGE:figures/full_fig_p074_3.png] view at source ↗
Figure 3
Figure 3. Figure 3 [PITH_FULL_IMAGE:figures/full_fig_p075_3.png] view at source ↗
Figure 3.4
Figure 3.4. Figure 3.4: Fp difference estimator for Fp(u + v) − Fp(u) with integer p > 2. bucket across all rows is tracked by the data structure. Then to estimate the frequency of each item i, the algorithm outputs the median of the values associated with each bucket that i is hashed to, across all rows. We recall the following guarantees for CountSketch algorithm: Theorem 3.5.38. [CCF04] Given ε ∈ (0, 1), there exists a strea… view at source ↗
Figure 3.5
Figure 3.5. Figure 3.5: Fp difference estimator for ⟨v, u p−1 ⟩ with integer p > 2. Thus, the variance is at most ∥u∥ 2 2 · γ 2/p∥u∥ 2 p · γ 1−2/p∥u∥ 2p−4 p ≤ γ n1−2/p ∥u∥ 2 p · ∥u∥ 2 p · ∥u∥ 2p−4 p . Therefore, for R = O  γ ε 2 n 1−2/p , it follows from Chebyshev’s inequality that with probability at least 2 3 , the difference estimator achieves an estimate to Fp(u + v) − Fp(u) with additive error ε p · Fp(v) approximation t… view at source ↗
Figure 4.1
Figure 4.1. Figure 4.1: Space bounds for black-box robust streaming algorithms for central problems in the [PITH_FULL_IMAGE:figures/full_fig_p101_4_1.png] view at source ↗
Figure 5.1
Figure 5.1. Figure 5.1: Attack on Real-Valued Sketches for F0 Estimation We now prove Theorem 5.2.1. Theorem 5.2.1. [GLW+24] Let A be a linear sketching algorithm with sketching matrix A ∈ R r×n , and suppose all nonzero subdeterminants of A are at least 1 poly(r) . Suppose A uses an estimator f : R r×n × R r → {−1, +1} to solve the (α + c, β − c)-gap F0 problem for constants α, β, c, and returns f(A, Ax) on each input x. Then,… view at source ↗
Figure 5.2
Figure 5.2. Figure 5.2: Reconstruction attack on linear sketches by [ [PITH_FULL_IMAGE:figures/full_fig_p142_5_2.png] view at source ↗
Figure 5
Figure 5. Figure 5 [PITH_FULL_IMAGE:figures/full_fig_p151_5.png] view at source ↗
Figure 5
Figure 5. Figure 5 [PITH_FULL_IMAGE:figures/full_fig_p155_5.png] view at source ↗
Figure 5.3
Figure 5.3. Figure 5.3: Differences in probability mass functions [PITH_FULL_IMAGE:figures/full_fig_p156_5_3.png] view at source ↗
Figure 5
Figure 5. Figure 5 [PITH_FULL_IMAGE:figures/full_fig_p159_5.png] view at source ↗
Figure 5
Figure 5. Figure 5 [PITH_FULL_IMAGE:figures/full_fig_p163_5.png] view at source ↗
Figure 5.4
Figure 5.4. Figure 5.4: Algorithm that generates an adaptive attack via a turnstile data stream. [PITH_FULL_IMAGE:figures/full_fig_p164_5_4.png] view at source ↗
Figure 5
Figure 5. Figure 5 [PITH_FULL_IMAGE:figures/full_fig_p165_5.png] view at source ↗
Figure 5
Figure 5. Figure 5 [PITH_FULL_IMAGE:figures/full_fig_p186_5.png] view at source ↗
Figure 5.5
Figure 5.5. Figure 5.5: Construction of our attack Proof. This statement and corresponding proof are almost identical to Lemma 2.4 in [SU15], with the difference that v is drawn from a different probability distribution, i.e., v ∼ Dp to handle the boundaries of [α, β], instead of the probability distribution in [SU15]. Since Pr v∼Dp [v = 0] = p, then we have E v∼Dp [ϕ p (c)] = p · ϕ p (−1) + (1 − p) · ϕ p (1). Due to the settin… view at source ↗
Figure 7.1
Figure 7.1. Figure 7.1: Adversarially robust F2 norm estimation algorithm on turnstile streams from [GLW+26b] Algorithm overview. The algorithm organizes the stream into a hierarchical tree structure. At the base level 1, the algorithm partitions the stream into blocks consisting of B individual updates, while each higher level aggregates B nodes from the level below into a single block. Every – 231 – [PITH_FULL_IMAGE:figures/… view at source ↗
Figure 7
Figure 7. Figure 7 [PITH_FULL_IMAGE:figures/full_fig_p233_7.png] view at source ↗
Figure 7.2
Figure 7.2. Figure 7.2: Illustration of the recursive tree decomposition of the stream of [ [PITH_FULL_IMAGE:figures/full_fig_p233_7_2.png] view at source ↗
Figure 7
Figure 7. Figure 7 [PITH_FULL_IMAGE:figures/full_fig_p241_7.png] view at source ↗
Figure 7
Figure 7. Figure 7 [PITH_FULL_IMAGE:figures/full_fig_p248_7.png] view at source ↗
Figure 7.3
Figure 7.3. Figure 7.3: Algorithm for adversarially robust heavy hitters in insertion-deletion streams. [PITH_FULL_IMAGE:figures/full_fig_p248_7_3.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

20 extracted references · 10 linked inside Pith

  1. [3]

    Private data stream analysis for universal symmetric norm estimation

    38 [BMWZ23] Vladimir Braverman, Joel Manning, Zhiwei Steven Wu, and Samson Zhou. Private data stream analysis for universal symmetric norm estimation. InApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, AP- PROX/RANDOM, pages 45:1–45:24, 2023. 244 [BNS+16] Raef Bassily, Kobbi Nissim, Adam D. Smith, Thomas Steinke, Ur...

    2023

  2. [11]

    Polynomial estimators for high frequency moments

    215, 216, 218, 219, 220, 221, 222, 223, 224 [Gan11] Sumit Ganguly. Polynomial estimators for high frequency moments. CoRR, abs/1104.4552, 2011. 55, 81, 82, 243 [Gan12] Sumit Ganguly. A lower bound for estimating high moments of a data stream.CoRR, abs/1201.0253, 2012. 81 – 269 – [GG11] Eran Gat and Shafi Goldwasser. Probabilistic search algorithms with un...

    Pith/arXiv arXiv 2011

  3. [15]

    Hamilton, Simon Lacoste-Julien, Pascal Vincent, and Gauthier Gidel

    179, 196 [MBB+22] Andjela Mladenovic, Avishek Joey Bose, Hugo Berard, William L. Hamilton, Simon Lacoste-Julien, Pascal Vincent, and Gauthier Gidel. Online adversarial attacks. In The Tenth International Conference on Learning Representations, ICLR, 2022. 10 [MBN+17] Slobodan Mitrovic, Ilija Bogunovic, Ashkan Norouzi-Fard, Jakub Tarnawski, and Volkan Cevh...

    Pith/arXiv arXiv 2022

  4. [16]

    Woodruff, and Sam- son Zhou

    71 [NPW+26] Soham Nagawanshi, Shalini Panthangi, Chen Wang, David P. Woodruff, and Sam- son Zhou. Learning-augmented moment estimation on time-decay models. In14th International Conference on Learning Representations, ICLR, 2026. 59 [NS17] Danupon Nanongkai and Thatchaphol Saranurak. Dynamic spanning forest with worst-case update time: adaptive, las vegas...

    2026

  5. [20]

    Woodruff and Qin Zhang

    46 [WZ12] David P. Woodruff and Qin Zhang. Tight bounds for distributed functional monitoring. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC, pages 941–960. ACM, 2012. 81, 256 [WZ21a] David P. Woodruff and Samson Zhou. Separations for estimating large frequency moments on data streams. In48th International Colloquium on Auto...

    2012

  6. [1971]

    Random sampling with a reservoir.ACM Trans

    27 [Vit85] Jeffrey Scott Vitter. Random sampling with a reservoir.ACM Trans. Math. Softw., 11(1):37–57, 1985. 111 [VX12a] Kasturi R. Varadarajan and Xin Xiao. A near-linear algorithm for projective clustering integer points. InProceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1329–1342, 2012. 42 [VX12b] Kasturi ...

    1985

  7. [1997]

    Approximate range searching in higher dimension

    106 [CLM08] Bernard Chazelle, Ding Liu, and Avner Magen. Approximate range searching in higher dimension. Computational Geometry, 39(1):24–29, 2008. 105 [CLN+22] Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Moshe Shechner, and Uri Stemmer. On the robustness of countsketch to adaptive inputs. InInternational Conference on Machine Learning, ICML, page...

    Pith/arXiv arXiv 2008

  8. [2003]

    Smooth histograms for sliding windows

    256 [BO07] Vladimir Braverman and Rafail Ostrovsky. Smooth histograms for sliding windows. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Proceedings, pages 283–293, 2007. 59 [BOS26] Omri Ben-Eliezer, Krzysztof Onak, and Sandeep Silwal. Robust streaming against low- memory adversaries. In17th Innovations in Theoretical Computer S...

    2007

  9. [2006]

    Mahoney, and S

    22, 96 – 267 – [DMM06] Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. Sampling algorithms for l2 regression and applications. InProceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1127–1136, 2006. 41, 43 [DMMW12] Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, and David P. Woodruff. Fast approxi...

    Pith/arXiv arXiv 2006

  10. [2010]

    Karp and Michael O

    89, 90, 132, 205, 243 [KR87] Richard M. Karp and Michael O. Rabin. Efficient randomized pattern-matching algorithms. IBM J. Res. Dev., 31(2):249–260, 1987. 212 [KR02] David R. Karger and Matthias Ruhl. Finding nearest neighbors in growth-restricted metrics. In Proceedings on 34th Annual ACM Symposium on Theory of Computing, pages 741–750, 2002. 106 [KSS22...

    Pith/arXiv arXiv 1987

  11. [2011]

    Woodruff

    132 [PW13] Eric Price and David P. Woodruff. Lower bounds for adaptive sparse recovery. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 652–663, 2013. 132 [RFP10] Benjamin Recht, Maryam Fazel, and Pablo A. Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization.S...

    Pith/arXiv arXiv 2013

  12. [2013]

    Randomized algorithms for tracking dis- tributed count, frequencies, and ranks.Algorithmica, 81(6):2222–2243, 2019

    8, 9, 12, 132, 134, 135, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 150, 151, 160, 161, 162, 163, 164, 165, 166, 167, 168, 171, 172, 174, 226 [HYZ19] Zengfeng Huang, Ke Yi, and Qin Zhang. Randomized algorithms for tracking dis- tributed count, frequencies, and ranks.Algorithmica, 81(6):2222–2243, 2019. 256 [IEM18] Andrew Ilyas, Logan Engs...

    Pith/arXiv arXiv 2019

  13. [2015]

    On the uniform convergence of relative frequencies of events to their probabilities.Theory of Probability & Its Applications, 16(2):264–280,

    214 [VC71] VN Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities.Theory of Probability & Its Applications, 16(2):264–280,

  14. [2016]

    Evasion attacks against machine learning at test time

    26, 67, 75 [BCM+13] Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Srndic, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. InMachine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD, Proceedings, Part III, pages 387–402, 2013. 10, 210 [BCP93] Hervé Br...

    Pith/arXiv arXiv 2013

  15. [2018]

    Generalization in adaptive data analysis and holdout reuse

    210 [DFH+15a] Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth. Generalization in adaptive data analysis and holdout reuse. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems, pages 2350–2358, 2015. 107, 112, 113 [DFH+15b] Cynthia Dwork, Vitaly Feld...

    2015

  16. [2019]

    Clustering on sliding windows in polylogarithmic space

    38 – 262 – [BLLM15] Vladimir Braverman, Harry Lang, Keith Levin, and Morteza Monemizadeh. Clustering on sliding windows in polylogarithmic space. In35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS, pages 350–364, 2015. 59 [BLLM16] Vladimir Braverman, Harry Lang, Keith Levin, and Morteza Monemizadeh...

    2015

  17. [2020]

    Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm, 2007

    38 [FFGM07] Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier. Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm, 2007. 253 [FFL+25] Shiyuan Feng, Ying Feng, George Z. Li, Zhao Song, David P. Woodruff, and Lichen Zhang. On differential privacy for adaptively solving search problems via sketching. CoRR, abs/250...

    Pith/arXiv arXiv 2007

  18. [2022]

    Woodruff

    253 [FMSW10] Dan Feldman, Morteza Monemizadeh, Christian Sohler, and David P. Woodruff. Coresets and sketches for high dimensional subspace approximation problems. InPro- ceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 630–649, 2010. 38 [Fre75] David A Freedman. On tail probabilities for martingales.the Annals of...

    2010

  19. [2023]

    Elements of information theory

    107, 253 [Cov99] Thomas M Cover. Elements of information theory. John Wiley & Sons, 1999. 22 [CP97] Joseph T Chang and David Pollard. Conditioning as disintegration. Statistica Neerlandica, 51(3):287–317, 1997. 134 [CP15] Michael B. Cohen and Richard Peng.lp row sampling by lewis weights. InProceedings of the Forty-Seventh Annual ACM on Symposium on Theor...

    Pith/arXiv arXiv 1999

  20. [2025]

    Woodruff, Huacheng Yu, and Samson Zhou

    150, 152, 153, 154, 155, 156, 157, 158, 161, 163, 164, 165, 166, 167, 168, 171, 172, 173, 175, 226 – 270 – [GLW+26a] Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, and Samson Zhou. Adversarial robustness for small frequency moments and a weak equivalence theorem for turnstile streams. InIEEE 67th Annual Symposium on Foundations of Computer ...

    2026