Pith. sign in

REVIEW 2 major objections 7 minor 278 references

First robust polylog-space F_p estimation for all p in [0,2]

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 · glm-5.2

2026-07-08 10:02 UTC pith:TZMGVZRT

load-bearing objection First (1+ε)-approximation for F_p (p in [0,2)) in adversarially robust turnstile streams; the convergence argument in Lemma 3.9 has a gap that needs explicit verification. the 2 major comments →

arxiv 2607.06312 v1 pith:TZMGVZRT submitted 2026-07-07 cs.DS

Adversarial Robustness for Small Frequency Moments and a Weak Equivalence Theorem for Turnstile Streams

Elena Gribelyuk , Honghao Lin , David P. Woodruff , Huacheng Yu , Samson Zhou This is my paper
classification cs.DS
keywords epsilonspacealgorithmfactorfrequencyincludingmomentsrobust
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.

This paper proves that for any constant p in [0,2] and any accuracy parameter epsilon, there exists an adversarially robust streaming algorithm that maintains a (1+epsilon)-approximation to the p-th frequency moment F_p at all times, using only poly(1/epsilon, log n) bits of space, even when an adversary chooses each stream update adaptively based on all previous algorithm outputs. This closes a central gap: prior work achieved this guarantee only for p=2, while for all other p in [0,2), including the distinct-elements problem F_0, only constant-factor approximations were known in sublinear space under adversarial updates. The key technical innovation is a generalization of the estimator-corrector-learner framework from Hilbert space (L_2) to general L_p spaces. The authors do this by observing that for any p in [0,2), there exists an isometric embedding f from L_p into a Hilbert space, so that distances in L_p become squared L_2 distances in the embedded space. The algorithm never explicitly computes this embedding (which is nonlinear and high-dimensional); instead, it performs all computations implicitly by estimating the required inner products in the embedded space using classical (non-robust) F_p sketches. When the estimator fails on a query, the learner updates its approximation by solving a regularized kernel ridge regression over previously seen hard queries, with the regularization ensuring bounded coefficients and controlled error accumulation. The paper also proves a weak equivalence theorem: for any sub-multiplicative norm, the existence of an efficient classical (oblivious) linear sketch is equivalent, up to polynomial factors, to the existence of an efficient adversarially robust turnstile algorithm. The bridge between the two models is L_1 embeddability: any norm that admits an oblivious sketch must embed into L_1 (or L_{1-epsilon}), and the authors' robust L_p estimation primitives can then simulate the sketch in the adversarial setting. As applications, the framework yields the first robust turnstile algorithms for Earth Mover Distance, k-median clustering, Shannon entropy, graph total variation, trend filtering, and losses defined by Bernstein functions.

Core claim

The central discovery is that the estimator-corrector-learner framework, previously limited to F_2 estimation in Hilbert space, can be extended to all F_p moments for p in [0,2] by exploiting the existence of isometric embeddings from L_p into L_2. The algorithm operates entirely in the original space, estimating inner products in the embedded Hilbert space indirectly through F_p norm sketches, and using regularized regression to maintain bounded-coefficient iterates that converge to the target vector. This convergence argument, combined with a multi-scale stratification converting additive error to multiplicative error, yields the first (1+epsilon)-approximation for F_0 and all F_p (p in [0

What carries the argument

Isometric embedding of L_p into L_2 (Schoenberg/Robertson), enabling implicit Hilbert-space geometry via F_p sketch estimates of embedded inner products; regularized kernel ridge regression over adaptively discovered hard queries to maintain bounded-coefficient iterates; multi-scale stratification converting additive to multiplicative error; L_1 embeddability as the bridge between oblivious sketching and adversarial robustness (via the Andoni-Krauthgamer-Razenshteyn equivalence of sketching and embedding for norms)

Load-bearing premise

The convergence argument in Lemma 3.9 requires that each time the estimator is inaccurate, the potential measuring distance to the target decreases by a factor of (1 - O(eta^2)), where eta = epsilon/H. But the algorithm only has access to approximate values of this potential through F_p sketches, with estimation error of the same order Theta(eta^2 * A) as the progress made. The net progress per step is determined by constant-factor differences between these two quantities, so

What would settle it

Construct an adaptive adversary that forces the learner to update its iterate on queries where the estimation error in the projected vector is at the high end of its allowed range, so that the potential decreases by less than the error incurred, causing the list size to grow unboundedly and the space to exceed poly(1/epsilon, log n).

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

If this is right

  • Any streaming statistic that can be reduced to F_p estimation for p in [0,2] now inherits adversarial robustness in the turnstile model, including entropy, EMD, k-median, and Bernstein-function losses.
  • The weak equivalence theorem means that classical sketching lower bounds now transfer to the robust setting, and new robust algorithms imply new linear sketches, providing a bidirectional tool for proving impossibility results.
  • The deterministic derandomization technique for EMD embeddings (concatenating over all grid shifts) may be applicable to other randomized embeddings that fail under adaptive inputs.
  • The implicit embedding approach suggests a general recipe: whenever an isometric embedding into L_2 exists but is nonconstructive, one can still design robust algorithms by estimating embedded-space inner products through oblivious sketches in the original space.

Where Pith is reading between the lines

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

  • The tightest part of the analysis is Lemma 3.9 (bounded list size), where the progress per learner update and the estimation error are both of order Theta(eta^2 * A). The paper asserts the constants work out, but the margin is thin: if the error in computing the projected iterate is slightly larger than the progress made, the list size could be unbounded, breaking the space bound. A cleaner separa
  • The weak equivalence is stated for sub-multiplicative norms and uses an advice model for the (possibly nonconstructive) embedding matrix. Whether the advice can be removed or made efficient for specific norms beyond the explicit cases (EMD, total variation) remains open.
  • The recursion depth H = O(log n) and the per-level error budget eta = epsilon/H suggest that the poly(1/epsilon, log n) space bound may have a high polynomial degree in 1/epsilon. Tightening the dependence on epsilon, perhaps through a more efficient recursion or a direct (non-recursive) estimator, would be a natural next step.

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

2 major / 7 minor

Summary. This paper studies adversarially robust streaming algorithms in the insertion-deletion (turnstile) model, where future updates may depend on past algorithm outputs. The main result (Theorem 1.2) establishes that for any constant p in [0,2] and any epsilon in (0,1), there exists an adversarially robust turnstile streaming algorithm that outputs a (1+epsilon)-approximation to the p-th frequency moment F_p at all times using poly(1/epsilon, log n) bits of space. This closes a significant gap: prior work achieved this guarantee only for p=2, while for p in [0,2) (including the distinct elements problem F_0), only constant-factor approximations were known in sublinear space. The approach generalizes the estimator-corrector-learner framework of prior work (GLW+26) to non-Hilbert spaces by using isometric embeddings of L_p into L_2, performing regularized kernel ridge regression over adaptively discovered hard queries, and carefully managing the recursion. The paper also establishes a weak equivalence theorem (Theorem 1.3) between classical oblivious sketching and adversarial robustness for sub-multiplicative norms, and gives applications to EMD, k-median clustering, entropy estimation, and Bernstein-function losses.

Significance. The central result—achieving (1+epsilon)-approximation for F_p (p in [0,2]) in the adversarially robust turnstile model with polylogarithmic space—is a substantial advance. The F_0 (distinct elements) case alone is a major open problem. The technical approach of implicitly simulating the estimator-corrector-learner framework in an embedded Hilbert space, without ever materializing the embedding, is novel and non-trivial. The recursion reduction (Lemma 3.1) that collapses O(L^2) potential recursive calls to a single one is a clean and important ingredient. The weak equivalence theorem (Theorem 1.3) provides a useful structural perspective. The applications to EMD, k-median, entropy, and Bernstein-function losses demonstrate the generality of the framework. The paper provides full pseudocode (Algorithms 1-4) and detailed proofs of the key lemmas.

major comments (2)
  1. Lemma 3.9 (Bounded list size), final paragraph: The convergence argument derives the multiplicative decrease ||y-y'||^2 <= (1 - eta^2/16) * ||y-w||^2 for the *exact* projection y' onto the augmented subspace. The algorithm, however, computes y' via GetIterate (Algorithm 4), which solves the regularized regression using approximate inner products from F_p sketches. The paper acknowledges this in the final paragraph: 'the argument above assumes that we compute the new projection y' exactly. However, Algorithm 1 computes distances to y' up to additive error Theta(epsilon^2 A / H^2).' This sentence conflates two distinct error sources: (a) the error in the algorithm's *estimate* of ||y-y'||^2 (which affects the corrector's decision), and (b) the error in y' *itself* due to solving the regression with approximate inner products (which affects the actual progress ||y - tilde{v}||^2). Source (b
  2. Theorem 1.3 (Weak equivalence), reverse direction: The proof of the reverse direction (robust to oblivious) is dispatched in a single sentence citing known results [LNW14, AHLW16, HLY19, JLY26]. However, these results typically show that turnstile streaming algorithms (under certain conditions) can be simulated by linear sketches, but the connection to the specific norm structure and the D-gap problem on the oblivious side is not made explicit. The theorem statement claims the resulting sketch achieves a D-approximation using O(s log n) bits, but the relationship between the robust algorithm's approximation factor D and the sketch's parameters is unclear from the cited results. A more detailed justification, even if standard, would strengthen this direction of the equivalence.
minor comments (7)
  1. Algorithm 1, line 14: The condition '(P_i + Q_i) in A_i ± 6i*epsilon/(100H)*A' uses ambiguous notation. It should specify whether this means |P_i + Q_i - A_i| <= 6i*epsilon*A/(100H) or something else. The same notation appears in Algorithm 2, line 6.
  2. Lemma 3.3, final inequality chain: The step from ||sum alpha_i f(q_i - q_L) - f(q_{L+1})||^2 <= ||v||^2 + O(A) + ||v||*O(sqrt(A)) to ||v||^2 + O(A) uses the bound ||v||^2 <= ||z||_p^p + O(A) from Lemma 2.5, but the intermediate step involving ||v||*O(sqrt(A)) is dropped without explicit justification. This should be made explicit.
  3. Section 1.2.1: The Hadamard code example is insightful but the transition from it to the embedding-based approach is somewhat abrupt. A sentence explicitly stating that the embedding into L_2 resolves the issue (because the L_2 geometry allows Pythagorean-type arguments) would help the reader.
  4. Lemma 3.6: The statement conditions on 'v being a fixed iterate vector in block C_{i,j} at level i, at a fixed time in the stream, conditioned on the previous times.' The precise meaning of 'conditioned on the previous times' could be stated more formally (e.g., conditioned on the sigma-algebra generated by the algorithm's randomness and adversary's choices up to this point).
  5. The space complexity analysis at the end of Theorem 1.2's proof sets B = O(1/eta^2 * log n) and H = O(log n), yielding log(1/delta) = O(1/eta^6 * log^4 n). A brief remark on how the final poly(1/epsilon, log n) bound emerges from these parameters (since eta = epsilon/H = epsilon/O(log n)) would aid verification.
  6. The paper uses both 'EstDot' (in the description following Lemma 2.4) and 'DotEst' (in Figure 1 and Algorithm 3) for the same subroutine. Pick one name.
  7. Reference [GLW+26] is cited as appearing in STOC 2026. If this is a forthcoming publication, please ensure the bibliographic details are complete and correct upon finalization.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and the positive assessment of our contributions. The referee raises two major comments, both concerning proof details: one about the convergence argument in Lemma 3.9 (Bounded list size) and one about the reverse direction of Theorem 1.3 (Weak equivalence). We address both below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: Lemma 3.9 (Bounded list size), final paragraph: The convergence argument derives the multiplicative decrease ||y-y'||^2 <= (1 - eta^2/16) * ||y-w||^2 for the *exact* projection y' onto the augmented subspace. The algorithm, however, computes y' via GetIterate (Algorithm 4), which solves the regularized regression using approximate inner products from F_p sketches. The paper acknowledges this in the final paragraph but conflates two distinct error sources: (a) the error in the algorithm's *estimate* of ||y-y'||^2 (which affects the corrector's decision), and (b) the error in y' *itself* due to solving the regression with approximate inner products (which affects the actual progress ||y - tilde{v}||^2).

    Authors: The referee is correct that the final paragraph of Lemma 3.9 does not adequately distinguish between the two error sources (a) and (b), and that a more careful argument is needed. We will revise this paragraph to separate the two concerns and address each explicitly. revision: yes

  2. Referee: Theorem 1.3 (Weak equivalence), reverse direction: The proof of the reverse direction (robust to oblivious) is dispatched in a single sentence citing known results [LNW14, AHLW16, HLY19, JLY26]. However, these results typically show that turnstile streaming algorithms (under certain conditions) can be simulated by linear sketches, but the connection to the specific norm structure and the D-gap problem on the oblivious side is not made explicit. The theorem statement claims the resulting sketch achieves a D-approximation using O(s log n) bits, but the relationship between the robust algorithm's approximation factor D and the sketch's parameters is unclear from the cited results. A more detailed justification, even if standard, would strengthen this direction of the equivalence.

    Authors: The referee is right that the reverse direction is dispatched too briefly. We will expand the proof to make the connection between the robust algorithm's approximation factor D and the resulting sketch's parameters explicit, rather than relying on a single citation. revision: yes

Circularity Check

0 steps flagged

No significant circularity; self-citation to [GLW+26] provides structural framework but central technical content is independent

full rationale

The paper builds on the estimator-corrector-learner framework of [GLW+26] (overlapping authors), but this citation provides a structural template rather than a result that makes the current claims true by construction. The central technical contributions — implicit isometric embeddings into L₂ via Schoenberg's theorem (Theorem 2.1, citing [Sch38, Sch35, Rob24] with no author overlap), regularized kernel ridge regression in sketch space (Algorithm 4, Lemma 3.4–3.5), the recursive decomposition reducing to a single squared-norm (Lemma 3.1), and the convergence analysis via Pythagorean theorem in the embedded space (Lemma 3.9) — are genuinely new and do not reduce to the F₂ result of [GLW+26]. The oblivious F_p sketches (Theorem 2.3) cite [Ind06, Li08, KNW10a, KNW10b, KNPW11] with no author overlap. The weak equivalence theorem (Theorem 1.3) relies on [AKR18] (no author overlap) for the forward direction and on [LNW14, AHLW16, HLY19, JLY26] for the reverse direction. Lemma 4.15 cites [GLW+26] for a non-robust Bernstein-function streaming algorithm, but this provides only the estimator subroutine; the robust guarantee comes from the new embedding and framework. No step in the derivation chain reduces to its own inputs by definition or by self-citation. The convergence argument in Lemma 3.9 has a potential correctness gap (approximation error Θ(η²A) vs. progress Θ(η²A)), but this is a rigor concern, not circularity — the output is not defined in terms of the input by construction.

Axiom & Free-Parameter Ledger

5 free parameters · 5 axioms · 1 invented entities

The paper introduces no new physical entities or postulated objects. The implicit embedded iterate is an algorithmic construct whose behavior is fully determined by the F_p sketch outputs. The regularization parameter ν is the main fitted parameter, chosen to control the condition number of the regression problem.

free parameters (5)
  • ε = input parameter
    Accuracy parameter, not fitted to data.
  • ν = ν₀√A where ν₀ = O(ε²/(H²√L)) = O(ε²/(H²√L))
    Regularization parameter chosen to bound the condition number κ = √L/ν₀ = L·H²/ε², ensuring coefficients α_i are bounded. Set in Algorithm 4 and §1.2.1.
  • H = O(log n) = O(log n)
    Number of recursion levels, set to ensure the input norm at the deepest level is O(1). Stated in space complexity analysis.
  • B = O(1/η² log n) = O(H²/ε² · log n)
    Number of blocks per level, set to ensure B ≥ L and BH ≥ m. Stated in space complexity analysis.
  • K = O(1/ε log n) = O(1/ε log n)
    Number of scale copies for multiplicative error conversion in §3.2.
axioms (5)
  • standard math Existence of isometric embeddings of L_p into Hilbert space (Theorem 2.1, citing [Sch38, Sch35, Rob24])
    Classical result in functional analysis; the paper uses existence only, not explicit construction.
  • standard math Oblivious F_p sketches achieve (1+ε)-approximation in O(1/ε² log²n) space (Theorem 2.3, citing [Ind06, Li08, KNW10a, KNW10b, KNPW11])
    Standard streaming result used as a black-box subroutine.
  • domain assumption Sketching and embedding are equivalent for norms (Theorem 4.2, citing [AKR18])
    Used for the weak equivalence theorem; due to authors with no overlap with the present paper.
  • domain assumption Bounded computation paths argument for robustness (used in proof of Theorem 1.2)
    Standard technique in adversarially robust streaming; the adversary is deterministic WLOG and the number of distinct transcripts is bounded.
  • domain assumption Frequency vector entries bounded by poly(n) (implicit throughout)
    Standard in turnstile streaming with m = poly(n); ensures the potential function starts at poly(n) and converges in O(1/η² log n) steps.
invented entities (1)
  • Implicit embedded iterate v = Σα_i·f(q_i) (no pre-image in original space) no independent evidence
    purpose: Approximates f(z) in the embedded Hilbert space; used as the learner's internal model.
    The iterate exists only in the embedded space and is manipulated via inner products computed from F_p sketches. It is not a new physical entity but an algorithmic construct; its correctness is verified through the corrector sketch.

pith-pipeline@v1.1.0-glm · 39309 in / 6406 out tokens · 352395 ms · 2026-07-08T10:02:30.612561+00:00 · methodology

0 comments
read the original abstract

We study adversarially robust algorithms for insertion-deletion (turnstile) streams, where future updates may depend on past algorithm outputs. While recent work achieved a robust $(1+\epsilon)$-approximation for the second moment $F_2$ in polylogarithmic space, achieving high accuracy for other frequency moments remained a major open question; for $p\in[0,2)$, including the fundamental distinct elements problem ($F_0$), only constant-factor approximations were known in sublinear space. We close this gap, showing that $(1+\epsilon)$-approximate robustness can be achieved in polylogarithmic space for all $p\in[0,2]$. Our approach generalizes the estimator-corrector-learner framework to non-Hilbert spaces by dynamically maintaining implicit isometric embeddings into $L_2$ and performing regularized kernel ridge regression over adaptively discovered hard queries, yielding the first insertion-deletion algorithms that approximate: (1) the $p$-th frequency moment $F_p$ up to a $(1+\epsilon)$-factor in poly$(1/\epsilon, \log n)$ space for all $p\in[0,2]$, including the support size $F_0$, (2) metric and information-theoretic quantities, including the Earth Mover Distance (EMD) and $k$-median clustering cost over $[\Delta]^d$ up to an $O(d \log \Delta)$-factor, and the Shannon entropy up to an $\epsilon$-additive error, and (3) non-normed symmetric losses defined by Bernstein functions up to a $(1+\epsilon)$-factor. For the $F_p$ moments, our algorithm is optimal up to poly$(1/\epsilon, \log n)$ factors. Furthermore, we establish a weak equivalence between classical oblivious sketching and adversarial robustness. We prove that for any sub-multiplicative norm, the existence of an efficient classical linear sketch is equivalent to the existence of an efficient robust turnstile algorithm, up to polynomial factors, formalizing $L_1$ embeddability as the fundamental mechanism governing both models.

Figures

Figures reproduced from arXiv: 2607.06312 by David P. Woodruff, Elena Gribelyuk, Honghao Lin, Huacheng Yu, Samson Zhou.

Figure 1
Figure 1. Figure 1: Estimator for dot product in the embedded space. [PITH_FULL_IMAGE:figures/full_fig_p014_1.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

278 extracted references · 278 canonical work pages

  1. [1]

    STOC 2021 Workshop , title =

    work page 2021

  2. [2]

    2026 , eprint=

    Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams , author =. 2026 , eprint=

    work page 2026

  3. [3]

    FOCS 2023 Workshop , title =

    work page 2023

  4. [4]

    EnCORE Workshop , title =

    work page

  5. [5]

    2009 , publisher=

    High-dimensional probability , author=. 2009 , publisher=

    work page 2009

  6. [6]

    CoRR , volume =

    Omri Ben-Eliezer and Sandeep Silwal and Krzysztof Onak , title =. CoRR , volume =

    work page

  7. [7]

    2013 , publisher=

    Classical Banach spaces II: function spaces , author=. 2013 , publisher=

    work page 2013

  8. [8]

    Kane and Jelani Nelson and Ely Porat and David P

    Daniel M. Kane and Jelani Nelson and Ely Porat and David P. Woodruff , title =. Proceedings of the 43rd

    work page

  9. [9]

    Sur la d

    Schoenberg, IJ , journal=. Sur la d

    work page

  10. [10]

    Bulletin of the Malaysian Mathematical Sciences Society , volume=

    Negative type and bi-lipschitz embeddings into Hilbert space , author=. Bulletin of the Malaysian Mathematical Sciences Society , volume=. 2024 , publisher=

    work page 2024

  11. [11]

    Transactions of the American Mathematical Society , volume=

    Metric spaces and positive definite functions , author=. Transactions of the American Mathematical Society , volume=. 1938 , publisher=

    work page 1938

  12. [12]

    Woodruff , title =

    Shiyuan Feng and William Swartworth and David P. Woodruff , title =. 52nd International Colloquium on Automata, Languages, and Programming,

    work page

  13. [13]

    Proceedings of the 57th Annual

    Mark Braverman and Or Zamir , title =. Proceedings of the 57th Annual

    work page

  14. [14]

    Woodruff and Lin F

    Vladimir Braverman and Emanuele Viola and David P. Woodruff and Lin F. Yang , title =. 45th International Colloquium on Automata, Languages, and Programming,

    work page

  15. [15]

    Approximation, Randomization, and Combinatorial Optimization

    Vladimir Braverman and Jonathan Katzman and Charles Seidell and Gregory Vorsanger , title =. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques,

    work page

  16. [16]

    Woodruff and Samson Zhou , title =

    Rajesh Jayaram and David P. Woodruff and Samson Zhou , title =. Proc

    work page

  17. [17]

    33rd Computational Complexity Conference,

    Sampath Kannan and Elchanan Mossel and Swagato Sanyal and Grigory Yaroslavtsev , title =. 33rd Computational Complexity Conference,

    work page

  18. [18]

    Proccedings of the 52nd Annual

    John Kallaugher and Eric Price , title =. Proccedings of the 52nd Annual

    work page

  19. [19]

    Nick Littlestone , title =. Mach. Learn. , volume =

    work page

  20. [20]

    Procopiuc and Divesh Srivastava and Thanh T

    Graham Cormode and Cecilia M. Procopiuc and Divesh Srivastava and Thanh T. L. Tran , title =. 15th International Conference on Database Theory,

    work page

  21. [21]

    Alexander Wei , title =

    work page

  22. [22]

    Thomas Dybdahl Ahle , title =. 58th

    work page

  23. [23]

    Rasmus Pagh , title =

    work page

  24. [24]

    Eyal Kushilevitz and Rafail Ostrovsky and Yuval Rabani , title =

    work page

  25. [25]

    Proceedings of the Thirtieth Annual

    Piotr Indyk and Rajeev Motwani , title =. Proceedings of the Thirtieth Annual

    work page

  26. [26]

    Lee , title =

    Robert Krauthgamer and James R. Lee , title =. Proceedings of the Fifteenth Annual

    work page

  27. [27]

    Kakade and John Langford , title =

    Alina Beygelzimer and Sham M. Kakade and John Langford , title =. Machine Learning, Proceedings of the Twenty-Third International Conference

    work page

  28. [28]

    Karger and Matthias Ruhl , title =

    David R. Karger and Matthias Ruhl , title =. Proceedings on 34th Annual

    work page

  29. [29]

    Clarkson , title =

    Kenneth L. Clarkson , title =. Proceedings of the Twenty-Ninth Annual

    work page

  30. [30]

    2022 , publisher=

    Introduction to algorithms , author=. 2022 , publisher=

    work page 2022

  31. [31]

    2008 , publisher=

    Computational geometry algorithms and applications , author=. 2008 , publisher=

    work page 2008

  32. [32]

    Woodruff , title =

    Eric Price and Zhao Song and David P. Woodruff , title =. 44th International Colloquium on Automata, Languages, and Programming,

    work page

  33. [33]

    Mark Dilman and Danny Raz , title =

    work page

  34. [34]

    Proceedings of the 2003

    Brian Babcock and Chris Olston , title =. Proceedings of the 2003

    work page 2003

  35. [35]

    CoRR , volume =

    Andrej Bogdanov and Alon Rosen and Neekon Vafa and Vinod Vaikuntanathan , title =. CoRR , volume =

    work page

  36. [36]

    Nguyen and David P

    Yi Li and Huy L. Nguyen and David P. Woodruff , title =. Symposium on Theory of Computing,

    work page

  37. [37]

    Woodruff , title =

    Yuqing Ai and Wei Hu and Yi Li and David P. Woodruff , title =. 31st Conference on Computational Complexity,

    work page

  38. [38]

    Crouch and Andrew McGregor and Daniel M

    Michael S. Crouch and Andrew McGregor and Daniel M. Stubbs , title =. Algorithms -

    work page

  39. [39]

    Studia Mathematica , volume=

    The best constants in the Khintchine inequality , author=. Studia Mathematica , volume=. 1981 , publisher=

    work page 1981

  40. [40]

    Ilya Mironov and Moni Naor and Gil Segev , title =

    work page

  41. [41]

    Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems , pages =

    Cameron Musco and Christopher Musco , title =. Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems , pages =

    work page

  42. [42]

    13th Innovations in Theoretical Computer Science Conference,

    Boaz Menuhin and Moni Naor , title =. 13th Innovations in Theoretical Computer Science Conference,

    work page

  43. [43]

    Theory of Cryptography - 20th International Conference,

    Moni Naor and Noa Oved , title =. Theory of Cryptography - 20th International Conference,

    work page

  44. [44]

    Gilbert and Brett Hemenway and Martin J

    Anna C. Gilbert and Brett Hemenway and Martin J. Strauss and David P. Woodruff and Mary Wootters , title =

    work page

  45. [45]

    Gilbert and Brett Hemenway and Atri Rudra and Martin J

    Anna C. Gilbert and Brett Hemenway and Atri Rudra and Martin J. Strauss and Mary Wootters , title =. 2012 Information Theory and Applications Workshop,

    work page 2012

  46. [46]

    Proceedings of the 25th

    Dmitrii Avdiukhin and Slobodan Mitrovic and Grigory Yaroslavtsev and Samson Zhou , title =. Proceedings of the 25th

    work page

  47. [47]

    Proceedings of the 35th International Conference on Machine Learning,

    Ehsan Kazemi and Morteza Zadimoghaddam and Amin Karbasi , title =. Proceedings of the 35th International Conference on Machine Learning,

    work page

  48. [48]

    Streaming Robust Submodular Maximization:

    Slobodan Mitrovic and Ilija Bogunovic and Ashkan Norouzi. Streaming Robust Submodular Maximization:. Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems , pages =

    work page

  49. [49]

    Mathematical Programming , volume=

    Robust monotone submodular function maximization , author=. Mathematical Programming , volume=. 2018 , publisher=

    work page 2018

  50. [50]

    , author=

    Robust Submodular Observation Selection. , author=. Journal of Machine Learning Research , volume=

    work page

  51. [51]

    Woodruff , title =

    Eric Price and David P. Woodruff , title =

    work page

  52. [52]

    Woodruff , title =

    Eric Price and David P. Woodruff , title =. Proceedings of the Twenty-Fourth Annual

    work page

  53. [53]

    Woodruff , title =

    Deanna Needell and William Swartworth and David P. Woodruff , title =. 63rd

    work page

  54. [54]

    Woodruff , title =

    William Swartworth and David P. Woodruff , title =. Proceedings of the 55th Annual

    work page

  55. [55]

    Conference modern analysis and probability, 1984 , pages=

    Extensions of Lipschitz mapping into Hilbert space , author=. Conference modern analysis and probability, 1984 , pages=

    work page 1984

  56. [56]

    Woodruff , title =

    David P. Woodruff , title =. Found. Trends Theor. Comput. Sci. , volume =

    work page

  57. [57]

    Muthukrishnan , title =

    Graham Cormode and S. Muthukrishnan , title =. J. Algorithms , volume =

    work page

  58. [58]

    Nicholas J. A. Harvey and Jelani Nelson and Krzysztof Onak , title =. 49th Annual

    work page

  59. [59]

    Meghal Gupta and Mihir Singhal and Hongxun Wu , title =. 65th

    work page

  60. [60]

    Shunhua Jiang and Binghui Peng and Omri Weinstein , title =. 64th

    work page

  61. [61]

    Cohen and Cameron Musco and Jakub Pachocki , title =

    Michael B. Cohen and Cameron Musco and Jakub Pachocki , title =. Theory Comput. , volume =

    work page

  62. [62]

    2007 , author=

    Derivations for linear algebra and optimization. 2007 , author=. URL: http://web. stanford. edu/\

    work page 2007

  63. [63]

    Woodruff and Taisuke Yasuda , title =

    David P. Woodruff and Taisuke Yasuda , title =. Proceedings of the 2023

    work page 2023

  64. [64]

    Varadarajan and Xin Xiao , title =

    Kasturi R. Varadarajan and Xin Xiao , title =. Proceedings of the Twenty-Third Annual

    work page

  65. [65]

    Varadarajan and Xin Xiao , title =

    Kasturi R. Varadarajan and Xin Xiao , title =

    work page

  66. [66]

    A new coreset framework for clustering , booktitle =

    Vincent Cohen. A new coreset framework for clustering , booktitle =

    work page

  67. [67]

    2024 , eprint=

    Unmasking Vulnerabilities: Cardinality Sketches under Adaptive Inputs , author=. 2024 , eprint=

    work page 2024

  68. [68]

    Improved Coresets for Euclidean k-Means , booktitle =

    Vincent Cohen. Improved Coresets for Euclidean k-Means , booktitle =

    work page

  69. [69]

    Towards optimal lower bounds for k-median and k-means coresets , booktitle =

    Vincent Cohen. Towards optimal lower bounds for k-median and k-means coresets , booktitle =

    work page

  70. [70]

    Clarkson and David P

    Kenneth L. Clarkson and David P. Woodruff , title =. Symposium on Theory of Computing Conference, STOC , pages =

    work page

  71. [71]

    Cohen and Cameron Musco and Christopher Musco , title =

    Michael B. Cohen and Cameron Musco and Christopher Musco , title =. Proceedings of the Twenty-Eighth Annual

    work page

  72. [72]

    Fast approximation of matrix coherence and statistical leverage , journal =

    Petros Drineas and Malik Magdon. Fast approximation of matrix coherence and statistical leverage , journal =

    work page

  73. [73]

    Mahoney and S

    Petros Drineas and Michael W. Mahoney and S. Muthukrishnan , title =. Proceedings of the Seventeenth Annual

    work page

  74. [74]

    Cohen and Richard Peng , title =

    Michael B. Cohen and Richard Peng , title =. Proceedings of the Forty-Seventh Annual

    work page

  75. [75]

    Woodruff and Samson Zhou , title =

    Vladimir Braverman and Petros Drineas and Cameron Musco and Christopher Musco and Jalaj Upadhyay and David P. Woodruff and Samson Zhou , title =. 61st

    work page

  76. [76]

    Vishnoi , title =

    Lingxiao Huang and Nisheeth K. Vishnoi , title =. Proccedings of the 52nd Annual

    work page

  77. [77]

    International Conference on Machine Learning,

    Murad Tukan and Samson Zhou and Alaa Maalouf and Daniela Rus and Vladimir Braverman and Dan Feldman , title =. International Conference on Machine Learning,

    work page

  78. [78]

    7th International Conference on Learning Representations,

    Cenk Baykal and Lucas Liebenwein and Igor Gilitschenski and Dan Feldman and Daniela Rus , title =. 7th International Conference on Learning Representations,

    work page

  79. [79]

    8th International Conference on Learning Representations,

    Ben Mussay and Margarita Osadchy and Vladimir Braverman and Samson Zhou and Dan Feldman , title =. 8th International Conference on Learning Representations,

    work page

  80. [80]

    Theory and Applications of Models of Computation, 16th International Conference,

    Murad Tukan and Cenk Baykal and Dan Feldman and Daniela Rus , title =. Theory and Applications of Models of Computation, 16th International Conference,

    work page

Showing first 80 references.