Pith. sign in

REVIEW 3 major objections 5 minor 64 references

Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters

T0 review · 3 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read 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)$.

desk verdict The heavy-hitter result is a real step, but the residual estimation subroutine has a scaling bug that breaks Theorem 1.3. read the letter →

arxiv 2412.05807 v1 pith:6XTKCKTV submitted 2024-12-08 cs.DS

David P. Woodruff , Samson Zhou This is my paper · ORCID
classification cs.DS MSC 68W2768W20
keywords adversarialstreamingturnstilestreamsLpnormestimationheavyhittersdense-sparsetradeoffsdifferentialprivacyresidualfrequencymoments
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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)$.

What carries the argument

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$.

What would settle it

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.

Watch

Extended reading notes

Core claim

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)})$.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

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).

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 (3)
  1. [§2 (Algorithm 2, Lemma 2.7)]
  2. [§3 (Algorithm 3, lines 13–16; Lemma 3.5)]
  3. [§3 (Lemma 3.5)]
minor comments (5)
  1. [Definition 3.1] 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.
  2. [Algorithm 3, line 7] 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.
  3. [Lemma 3.5] The proof contains an incomplete sentence: 'We that we achieve a (1+O~(ε))-approximation...'.
  4. [Lemma 2.5] 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.
  5. [§5 (Empirical Evaluations)] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No load-bearing circularity; the central derivation relies on external black-box results, and the few self-citations are not load-bearing.

full rationale

I examined the full derivation chain. Theorem 1.2 depends on DetHH from [GM07], CountSketch from [CCF04], RobustCS from [CLN+22], and LZeroEst from [KNW10]; all are external black boxes with stated space bounds, and Lemma 2.7 computes the total space directly from those bounds without fitting any parameter to the claimed conclusion. The residual estimator in Section 3 uses the subsampling framework of [IW05] and a level-set parameter M fixed from m and p in Definition 3.1; M is not chosen from the target Fp, so the estimate is not defined in terms of the quantity it predicts. Algorithm 4 combines SparseRecover [GSTV07], RobustHH, and ResidualEst with the standard differential-privacy robustification of Theorem 1.8, which cites [HKM+20, BKM+22, ACSS23, CSW+23]; although one of these four sources includes the present authors, the result is independently supported by the other three and by the surrounding standard DP machinery, so the self-citation is not load-bearing. No uniqueness theorem from the authors is invoked, and no ansatz is imported solely from the authors' prior work. I did find two non-circular concerns: Algorithm 2 initializes DetHH with universe parameter t while coordinates come from [n], so the Lemma 2.7 space bound may require an additional universe-reduction argument; and Algorithm 3 with Lemma 3.5 appears to scale level contributions by (1+eta)^l rather than by the roughly zeta M/(1+eta)^l per-item contribution in Definition 3.1, which is an internal correctness issue. Neither concern makes the derivation equivalent to its inputs by construction. Therefore the circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim does not fit constants to data; all balancing quantities are derived expressions in epsilon, m, and p. No invented entities are introduced. The main ledger item is the unstated assumption that DetHH can be run on a reduced universe of size equal to the L0 threshold; this is load-bearing for Theorem 1.2 and Theorem 1.3. The other axioms are standard DP and concentration results inherited from prior work.

assumptions (4)
  • ad hoc to paper DetHH can be applied when the number of distinct stream elements is at most O(t), even though the ambient universe is [n] and DetHH's space in Theorem 2.1 depends on a universe size parameter t.
    Algorithm 2 sets t as an L0 threshold and charges DetHH space only t^(2-2/p); no explicit dictionary, hash, or universe-reduction argument is given in Section 2. If Theorem 2.1 requires the ambient domain size, the space analysis in Lemma 2.7 does not follow.
  • standard math The DP-robustness framework of Theorem 1.8 applies to ResidualEst and LZeroEst when each instance answers with constant failure probability and the queries are adaptive.
    Used in Section 4 to amplify success probability and handle adaptive queries; this is standard machinery from HKM+20, BKM+22, ACSS23, and CSW+23.
  • domain assumption The update vector within a block satisfies ||v||_1 <= min(epsilon * M * k^(1-1/p) / 100, ||g||_1 / 2), so Lemma 4.4 applies.
    Lemma 4.4 is invoked in Lemma 4.5 using only the upper bound ||v||_1 <= ell; the second constraint ||v||_1 <= ||g||_1 / 2 is not justified in the dense case, though it is plausibly implied by the dense-state lower bound.
  • standard math Standard concentration and norm inequalities hold, including Chebyshev, Chernoff, Markov, and Lp monotonicity.
    Used throughout Sections 2 and 3 for the analysis of subsampling and heavy-hitter estimation.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters." pith.science (2026). https://pith.science/paper/6XTKCKTV

@misc{pith2026241205807,
  author       = {Pith},
  title        = {Pith review of: Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6XTKCKTV}},
  note         = {Machine review of arXiv:2412.05807}
}
abstract

In the adversarial streaming model, the input is a sequence of adaptive updates that defines an underlying dataset and the goal is to approximate, collect, or compute some statistic while using space sublinear in the size of the dataset. In 2022, Ben-Eliezer, Eden, and Onak showed a dense-sparse trade-off technique that elegantly combined sparse recovery with known techniques using differential privacy and sketch switching to achieve adversarially robust algorithms for $L_p$ estimation and other algorithms on turnstile streams. In this work, we first give an improved algorithm for adversarially robust $L_p$-heavy hitters, utilizing deterministic turnstile heavy-hitter algorithms with better tradeoffs. We then utilize our heavy-hitter algorithm to reduce the problem to estimating the frequency moment of the tail vector. We give a new algorithm for this problem in the classical streaming setting, which achieves additive error and uses space independent in the size of the tail. We then leverage these ingredients to give an improved algorithm for adversarially robust $L_p$ estimation on turnstile streams.

Figures

Figures reproduced from arXiv: 2412.05807 by the authors.

Figure 1
Figure 1. Empirical evaluations on the CAIDA dataset, comparing flip number of the [PITH_FULL_IMAGE:figures/full_fig_p020_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

64 extracted references · 54 canonical work pages

  1. [1]

    Adversarial laws of large numbers and optimal regret in online classification

    Noga Alon, Omri Ben - Eliezer, Yuval Dagan, Shay Moran, Moni Naor, and Eylon Yogev. Adversarial laws of large numbers and optimal regret in online classification. In STOC : 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages 447--455, 2021

    work page 2021

  2. [2]

    Woodruff

    Alexandr Andoni, Khanh Do Ba, Piotr Indyk, and David P. Woodruff. Efficient sketches for earth-mover distance, with applications. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS , pages 324--330, 2009

    work page 2009

  3. [3]

    Coloring in graph streams via deterministic and adversarially robust algorithms

    Sepehr Assadi, Amit Chakrabarti, Prantar Ghosh, and Manuel Stoeckl. Coloring in graph streams via deterministic and adversarially robust algorithms. In Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS , pages 141--153, 2023

    work page 2023

  4. [4]

    A framework for adversarial streaming via differential privacy and difference estimators

    Idan Attias, Edith Cohen, Moshe Shechner, and Uri Stemmer. A framework for adversarial streaming via differential privacy and difference estimators. In 14th Innovations in Theoretical Computer Science Conference, ITCS , pages 8:1--8:19, 2023

    work page 2023

  5. [5]

    Earth mover distance over high-dimensional spaces

    Alexandr Andoni, Piotr Indyk, and Robert Krauthgamer. Earth mover distance over high-dimensional spaces. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 343--352, 2008

    work page 2008

  6. [6]

    The space complexity of approximating the frequency moments

    Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. J. Comput. Syst. Sci. , 58(1):137--147, 1999

    1999

  7. [7]

    Adversarially robust submodular maximization under knapsack constraints

    Dmitrii Avdiukhin, Slobodan Mitrovic, Grigory Yaroslavtsev, and Samson Zhou. Adversarially robust submodular maximization under knapsack constraints. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD , pages 148--156, 2019

    work page 2019

  8. [8]

    Chestnut, Robert Krauthgamer, and Lin F

    Jaroslaw Blasiok, Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, and Lin F. Yang. Streaming symmetric norms via measure concentration. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC , pages 716--729, 2017

    work page 2017

Show all 64 references
  1. [9]

    Woodruff, and Samson Zhou

    Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, and Samson Zhou. Near optimal linear algebra in the online and sliding window models. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS , pages 517--528, 2020

    2020

  2. [10]

    Adversarially robust streaming via dense-sparse trade-offs

    Omri Ben - Eliezer, Talya Eden, and Krzysztof Onak. Adversarially robust streaming via dense-sparse trade-offs. In 5th Symposium on Simplicity in Algorithms, SOSA , 2022. (to appear)

    2022

  3. [11]

    Adversarial robustness of streaming algorithms through importance sampling

    Vladimir Braverman, Avinatan Hassidim, Yossi Matias, Mariano Schain, Sandeep Silwal, and Samson Zhou. Adversarial robustness of streaming algorithms through importance sampling. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Pr...

    2021

  4. [12]

    Razenshteyn, and David P

    Arturs Backurs, Piotr Indyk, Ilya P. Razenshteyn, and David P. Woodruff. Nearly-optimal bounds for sparse recovery in generic norms, with applications to k-median sketching. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 318...

    2016

  5. [13]

    Woodruff, and Eylon Yogev

    Omri Ben - Eliezer, Rajesh Jayaram, David P. Woodruff, and Eylon Yogev. A framework for adversarially robust streaming algorithms. J. ACM , 69(2):17:1--17:33, 2022

    2022

  6. [14]

    Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds

    Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer. Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds. In STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 1671--1684, 2022

    2022

  7. [15]

    Robust submodular maximization: A non-uniform partitioning approach

    Ilija Bogunovic, Slobodan Mitrovic, Jonathan Scarlett, and Volkan Cevher. Robust submodular maximization: A non-uniform partitioning approach. In Proceedings of the 34th International Conference on Machine Learning, ICML , pages 508--516, 2017

    2017

  8. [16]

    Private data stream analysis for universal symmetric norm estimation

    Vladimir Braverman, Joel Manning, Zhiwei Steven Wu, and Samson Zhou. Private data stream analysis for universal symmetric norm estimation. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM , pages 45:1--45:24, 2023

    2023

  9. [17]

    Smith, Thomas Steinke, Uri Stemmer, and Jonathan R

    Raef Bassily, Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, and Jonathan R. Ullman. Algorithmic stability for adaptive data analysis. SIAM J. Comput. , 50(3), 2021

    2021

  10. [18]

    Symmetric norm estimation and regression on sliding windows

    Vladimir Braverman, Viska Wei, and Samson Zhou. Symmetric norm estimation and regression on sliding windows. In Computing and Combinatorics - 27th International Conference, COCOON , Proceedings , pages 528--539, 2021

    2021

  11. [19]

    The adversarial robustness of sampling

    Omri Ben - Eliezer and Eylon Yogev. The adversarial robustness of sampling. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS , pages 49--62, 2020

    2020

  12. [20]

    The caida ucsd anonymized internet traces

    CAIDA. The caida ucsd anonymized internet traces. https://www.caida.org/catalog/datasets/passive_dataset, 2016

    2016

  13. [21]

    Chen, and Martin Farach - Colton

    Moses Charikar, Kevin C. Chen, and Martin Farach - Colton. Finding frequent items in data streams. Theor. Comput. Sci. , 312(1):3--15, 2004

    2004

  14. [22]

    Streaming euclidean MST to a constant factor

    Xi Chen, Vincent Cohen - Addad, Rajesh Jayaram, Amit Levi, and Erik Waingarten. Streaming euclidean MST to a constant factor. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC , pages 156--169, 2023

    2023

  15. [23]

    Adversarially robust coloring for graph streams

    Amit Chakrabarti, Prantar Ghosh, and Manuel Stoeckl. Adversarially robust coloring for graph streams. In 13th Innovations in Theoretical Computer Science Conference, ITCS , pages 37:1--37:23, 2022

    2022

  16. [24]

    New streaming algorithms for high dimensional EMD and MST

    Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten. New streaming algorithms for high dimensional EMD and MST . In STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 222--233, 2022

    2022

  17. [25]

    On the robustness of countsketch to adaptive inputs

    Edith Cohen, Xin Lyu, Jelani Nelson, Tam \' a s Sarl \' o s, Moshe Shechner, and Uri Stemmer. On the robustness of countsketch to adaptive inputs. In International Conference on Machine Learning, ICML , pages 4112--4140, 2022

    2022

  18. [26]

    On adaptive distance estimation

    Yeshwanth Cherapanamjeri and Jelani Nelson. On adaptive distance estimation. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS , 2020

    2020

  19. [27]

    Woodruff, Fred Zhang, Qiuyi Zhang, and Samson Zhou

    Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Fred Zhang, Qiuyi Zhang, and Samson Zhou. Robust algorithms on adaptive inputs from bounded adversaries. In The Eleventh International Conference on Learning Representations, ICLR , 2023

    2023

  20. [28]

    Clarkson and David P

    Kenneth L. Clarkson and David P. Woodruff. Numerical linear algebra in the streaming model. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC , pages 205--214, 2009

    2009

  21. [29]

    Woodruff, and Samson Zhou

    Vincent Cohen - Addad, David P. Woodruff, and Samson Zhou. Streaming euclidean k-median and k-means with o(log n) space. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS , pages 883--908, 2023

    2023

  22. [30]

    Preserving statistical validity in adaptive data analysis

    Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth. Preserving statistical validity in adaptive data analysis. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC , pages 117--126. ACM , 2015

    2015

  23. [31]

    Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography, Third Theory of Cryptography Conference, TCC , Proceedings , pages 265--284, 2006

    2006

  24. [32]

    Rothblum, and Salil P

    Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. Boosting and differential privacy. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS , pages 51--60, 2010

    2010

  25. [33]

    Woodruff, and Samson Zhou

    Itai Dinur, Uri Stemmer, David P. Woodruff, and Samson Zhou. On differential privacy and adaptive data analysis with bounded space. In Advances in Cryptology - EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Pro...

    2023

  26. [34]

    An approximate l1-difference algorithm for massive data streams

    Joan Feigenbaum, Sampath Kannan, Martin Strauss, and Mahesh Viswanathan. An approximate l1-difference algorithm for massive data streams. SIAM J. Comput. , 32(1):131--151, 2002

    2002

  27. [35]

    Woodruff

    Dan Feldman, Morteza Monemizadeh, Christian Sohler, and David P. Woodruff. Coresets and sketches for high dimensional subspace approximation problems. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 630--649, 2010

    2010

  28. [36]

    Gilbert, Brett Hemenway, Martin J

    Anna C. Gilbert, Brett Hemenway, Martin J. Strauss, David P. Woodruff, and Mary Wootters. Reusable low-error compressive sampling schemes through privacy. In IEEE Statistical Signal Processing Workshop, SSP , pages 536--539, 2012

    2012

  29. [37]

    Woodruff, Huacheng Yu, and Samson Zhou

    Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, and Samson Zhou. A strong separation for adversarially robust l_0 estimation for linear sketches. CoRR , abs/2409.16153, 2024

    2024 arXiv

  30. [38]

    Cr-precis: A deterministic summary structure for update data streams

    Sumit Ganguly and Anirban Majumder. Cr-precis: A deterministic summary structure for update data streams. In Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, First International Symposium, ESCAPE , pages 48--59, 2007

    2007

  31. [39]

    Gilbert, Martin J

    Anna C. Gilbert, Martin J. Strauss, Joel A. Tropp, and Roman Vershynin. One sketch for all: fast algorithms for compressed sensing. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing , pages 237--246, 2007

    2007

  32. [40]

    Adversarially robust streaming algorithms via differential privacy

    Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer. Adversarially robust streaming algorithms via differential privacy. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS , 2020

    2020

  33. [41]

    Nicholas J. A. Harvey, Jelani Nelson, and Krzysztof Onak. Sketching and streaming entropy via approximation theory. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS , pages 489--498, 2008

    2008

  34. [42]

    Woodruff

    Moritz Hardt and David P. Woodruff. How robust are linear sketches to adaptive inputs? In Symposium on Theory of Computing Conference, STOC , pages 121--130, 2013

    2013

  35. [43]

    Algorithms for dynamic geometric problems over data streams

    Piotr Indyk. Algorithms for dynamic geometric problems over data streams. In L \' a szl \' o Babai, editor, Proceedings of the 36th Annual ACM Symposium on Theory of Computing , pages 373--380, 2004

    2004

  36. [44]

    Woodruff

    Piotr Indyk and David P. Woodruff. Optimal approximations of the frequency moments of data streams. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing , pages 202--208, 2005

    2005

  37. [45]

    T. S. Jayram and David P. Woodruff. The data stream space complexity of cascaded norms. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS , pages 765--774, 2009

    2009

  38. [46]

    Woodruff, and Samson Zhou

    Rajesh Jayaram, David P. Woodruff, and Samson Zhou. Streaming algorithms with few state changes. In Proceedings of the 43rd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS , 2024

    2024

  39. [47]

    Brendan McMahan, Carlos Guestrin, and Anupam Gupta

    Andreas Krause, H. Brendan McMahan, Carlos Guestrin, and Anupam Gupta. Selecting observations against adversarial objectives. In Advances in Neural Information Processing Systems 20, Proceedings of the Twenty-First Annual Conference on Neural Information Processing Systems , p...

    2007

  40. [48]

    Separating adaptive streaming from oblivious streaming using the bounded storage model

    Haim Kaplan, Yishay Mansour, Kobbi Nissim, and Uri Stemmer. Separating adaptive streaming from oblivious streaming using the bounded storage model. In Advances in Cryptology - CRYPTO - 41st Annual International Cryptology Conference, CRYPTO Proceedings, Part III , pages 94--121, 2021

    2021

  41. [49]

    Kane, Jelani Nelson, and David P

    Daniel M. Kane, Jelani Nelson, and David P. Woodruff. An optimal algorithm for the distinct elements problem. In Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS , pages 41--52, 2010

    2010

  42. [50]

    Sketch-based change detection: methods, evaluation, and applications

    Balachander Krishnamurthy, Subhabrata Sen, Yin Zhang, and Yan Chen. Sketch-based change detection: methods, evaluation, and applications. In Proceedings of the 3rd ACM SIGCOMM Internet Measurement Conference, IMC , pages 234--247, 2003

    2003

  43. [51]

    Scalable deletion-robust submodular maximization: Data summarization with privacy and fairness constraints

    Ehsan Kazemi, Morteza Zadimoghaddam, and Amin Karbasi. Scalable deletion-robust submodular maximization: Data summarization with privacy and fairness constraints. In Proceedings of the 35th International Conference on Machine Learning, ICML , 2018

    2018

  44. [52]

    Woodruff

    Roie Levin, Anish Prasad Sevekari, and David P. Woodruff. Robust subspace approximation in a stream. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems, NeurIPS , 2018

    2018

  45. [53]

    Streaming robust submodular maximization: A partitioned thresholding approach

    Slobodan Mitrovic, Ilija Bogunovic, Ashkan Norouzi - Fard, Jakub Tarnawski, and Volkan Cevher. Streaming robust submodular maximization: A partitioned thresholding approach. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Proces...

    2017

  46. [54]

    Sketching in adversarial environments

    Ilya Mironov, Moni Naor, and Gil Segev. Sketching in adversarial environments. SIAM J. Comput. , 40(6):1845--1870, 2011

    2011

  47. [55]

    Razenshteyn, David P

    Sepideh Mahabadi, Ilya P. Razenshteyn, David P. Woodruff, and Samson Zhou. Non-adaptive adaptive sampling on turnstile streams. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC , pages 1251--1264, 2020

    2020

  48. [56]

    Woodruff, and Samson Zhou

    Sepideh Mahabadi, David P. Woodruff, and Samson Zhou. Adaptive sketches for robust regression with importance sampling. In Amit Chakrabarti and Chaitanya Swamy, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM ) , ...

    2022

  49. [57]

    Bloom filters in adversarial environments

    Moni Naor and Eylon Yogev. Bloom filters in adversarial environments. ACM Trans. Algorithms , 15(3):35:1--35:30, 2019

    2019

  50. [58]

    Orlin, Andreas S

    James B. Orlin, Andreas S. Schulz, and Rajan Udwani. Robust monotone submodular function maximization. Math. Program. , 172(1-2):505--537, 2018

    2018

  51. [59]

    Tabulation based 4-universal hashing with applications to second moment estimation

    Mikkel Thorup and Yin Zhang. Tabulation based 4-universal hashing with applications to second moment estimation. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 615--624, 2004

    2004

  52. [60]

    Woodruff, and Samson Zhou

    Ameya Velingker, Maximilian V \" o tsch, David P. Woodruff, and Samson Zhou. Fast (1+ \( \) )-approximation algorithms for binary matrix factorization. In International Conference on Machine Learning, ICML , pages 34952--34977, 2023

    2023

  53. [61]

    Woodruff and Taisuke Yasuda

    David P. Woodruff and Taisuke Yasuda. Online lewis weight sampling. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 4622--4666, 2023

    2023

  54. [62]

    Woodruff and Qin Zhang

    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, 2012

    2012

  55. [63]

    Woodruff and Samson Zhou

    David P. Woodruff and Samson Zhou. Separations for estimating large frequency moments on data streams. In 48th International Colloquium on Automata, Languages, and Programming, ICALP , pages 112:1--112:21, 2021

    2021

  56. [64]

    Woodruff and Samson Zhou

    David P. Woodruff and Samson Zhou. Tight bounds for adversarially robust streams and sliding windows via difference estimators. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS , pages 1183--1196, 2021

    2021

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.