Pith. sign in

REVIEW 6 major objections 5 minor 48 references

On Sketching Trimmed Statistics

T0 review · 6 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read This paper establishes that the top-k F_p moment of a frequency vector can be estimated in poly(log n/eps) space exactly when the k-th largest entry dominates the average squared tail, with matching upper and lower bounds.

desk verdict Genuine sublinear-space algorithms for top-k and trimmed-k F_p moments, but the sharp 'if and only if' threshold is overstated and the lower-bound section needs repair. read the letter →

arxiv 2506.07342 v2 pith:Z3NCNIR2 submitted 2025-06-09 cs.DS

Honghao Lin , Hoai-An Nguyen , David P. Woodruff This is my paper
classification cs.DS MSC 68W2068Q17
keywords streamingalgorithmsfrequencymomentstop-kF_pmomenttrimmedstatisticslinearsketchesheavyhittersCount-Sketchh-index
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 asks whether order-based statistics of a frequency stream, specifically the sum of the p-th powers of the k largest entries and the sum after discarding the largest and smallest k entries, can be approximated in sublinear space. It answers yes for p in [0,2], giving linear sketches that use poly(log n/eps) bits whenever k is moderately large, and more generally whenever the k-th largest value dominates the average squared tail. The paper also proves this dominance condition is essentially sharp, with a lower bound of $\Omega$($eps^{{-2}}$ n/k) bits when the k-th largest value is too small. These are the first sublinear-space algorithms for trimmed F_p statistics, and they improve the space needed for impact indices such as the h-index.

What carries the argument

The engine is a multi-level subsampling scheme combined with a level-set decomposition. Coordinates are grouped into exponentially growing intervals [zeta(1+eps)^{t-j-1}, zeta(1+eps)^{t-j}) with a random offset zeta, and for O(log n) subsampling rates the algorithm maintains an $\ell^2$ heavy-hitter structure, implemented as a small Count-Sketch, on the subsampled stream. For each contributing level set it finds the coarsest subsampling level at which about Theta(log n/$eps^{2}$) survivors appear, estimates the level size by re-scaling the survivor count, and sums the estimated contributions. The analytical novelty is a refined multi-level comparison showing that the threshold condition on $a_k^{2}$ forces each contributing level to dominate the residual norm after rank(v), so the Count-Sketch tail error stays below the level value v and every surviving heavy coordinate is identified.

What would settle it

Run the level-set estimator on a vector engineered to sit at the threshold, with $a_k^{2}$ equal to (eps/log n)^c times the average squared tail and a contributing level set whose lower endpoint equals a_k/(1+eps), and check whether the estimated level size stays within (1±eps) of the true count. A miss of even one surviving coordinate in that level would violate the paper's key lemma and the theorem's guarantee. Alternatively, feed the 2-SUM hard instance from the paper's lower bound to any poly(log n/eps)-space sketch; if it returns a (1±eps) answer, the claimed $\Omega$($eps^{{-2}}$ n/k) lower bound is false.

Watch

Extended reading notes

Core claim

The paper's central claim is that sublinear-space approximation of the top-k F_p moment for p in [0,2] is governed by a single ratio: compare $a_k^{2}$, the square of the k-th largest absolute frequency, with ||x_{-k}||$_2^{2}$ / k, the average squared tail mass. When $a_k^{2}$ >= (eps/log n)^c * ||x_{-k}||$_2^{2}$ / k, the level-set estimator returns a (1±eps) approximation of sum_{i=1}^k |a_i|^p using poly(log n/eps) bits, and the condition is automatically satisfied for k >= n/polylog n. When instead $a_k^{2}$ <= c*(k/n)*||x_{-k}||$_2^{2}$/k, any O(1)-pass streaming algorithm requires $\Omega$($eps^{{-2}}$ n/k) bits, so the threshold is structurally sharp. The trimmed-k statistic is computed by subtracting two top-moment estimates made on the same level sets, which cancels the top contribution and leaves an unavoidable additive error of O(eps)*(sum_{i=k}^{n-k} |a_i|^p + k|a_{k-eps k}|^p). For p>2 the same algorithms carry an extra $n^{{1-2/p}}$ factor that matches the known lower bound for global F_p estimation.

Load-bearing premise

The argument depends on the sub-sampled Count-Sketch being strong enough to identify every surviving coordinate of every contributing level set; if the tail error after subsampling is even slightly too large relative to the level value, the estimated level sizes and the final moment are no longer (1±eps)-accurate.

Editorial extensions

If this is right

  • For k >= n/polylog n, the dominance condition is automatically met, so the top-k F_p moment for p in [0,2] can be estimated in poly(log n/eps) bits with no additional assumption on the tail.
  • When the F_p mass of the top k coordinates is comparable to that of the tail, the same estimate gives a (1±eps) estimate of the k-residual error, improving the earlier residual-error sketch by a k^{2/p} factor.
  • The algorithm yields poly(log n/eps)-space estimators for thresholded F_p sums and for the g-, h-, and a-indices, including a (1±eps) approximation of the h-index that improves on prior space bounds that scale polynomially with n.
  • For p>2, the same multi-level sketches require poly(log n/eps)*n^{1-2/p} bits, and the n^{1-2/p} factor is provably unavoidable.
  • Because the sketches are linear, they extend to distributed and mergeable streaming settings without additional passes.

Reading between the lines

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

  • If the threshold characterization extends in the natural way, the same ratio of the k-th largest value to the average squared tail is likely to govern other order-based streaming statistics, such as relative-error approximations of arbitrary order statistics, which the paper does not address.
  • The 2-SUM reduction suggests a two-party communication analogue of the result: the same n/k threshold should characterize the communication cost of approximating top-k moments in distributed settings, a consequence the paper leaves implicit.
  • A practical extension is an adaptive sketch that tests the threshold condition online and switches from poly-log space to a larger Count-Sketch when the data violate it, since the experiments indicate the constant factors are small on skewed data.
  • One can probe the constant-factor gap in the level-set analysis directly by building a vector whose contributing level set starts at v = a_k/(1+eps); if survivors are missed there, the poly(eps/log n) exponent in the condition may be reducible.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

6 major / 5 minor

Summary. The manuscript studies one-pass linear sketching of the F_p moment of the top-k coordinates and of the trimmed-k vector (the vector obtained by deleting the largest and smallest k entries). For p in [0,2], it gives a level-set and sub-sampled Count-Sketch algorithm (Theorem 4.1, Section 4) that, under the tail condition a_k^2 >= (eps/log n)^c * ||x_-k||_2^2 / k, estimates the top-k F_p moment to (1 +/- eps) in poly(log n / eps) space, and a similar trimmed-k estimator with an additional additive error term (Theorem 5.1). Theorems 6.1 and 6.4 extend the results to p > 2 with a factor n^{1-2/p}. Section 7 derives applications to thresholded F_p and to g-, h-, and a-index moments, claiming an improvement over the h-index algorithm of Govindan, Monemizadeh, and Muthukrishnan. Section 8 gives lower bounds: Lemma 8.1 claims Omega(eps^{-2} n/k) space when a_k^2 <= c (k/n) ||x_-k||_2^2 / k, Lemma 8.6 an Omega(n/k^3) bound for O(k^p) approximation, and Lemma 8.11 an Omega(eps^{-2} log k) bound for the trimmed-k additive error. Section 9 reports experiments on synthetic, AOL, and CAIDA data.

Significance. If the upper-bound theorems are correct, the paper makes a useful contribution: it is the first to show that the top-k and trimmed-k F_p moments can be estimated in poly(log n / eps) space when the k-th order statistic dominates the average tail energy, and the multi-level residual comparison in Lemmas 4.3 and 5.5 is a genuine technical idea. The applications to thresholded F_p and impact indices, together with the experimental comparison against Count-Sketch, add value. However, the headline claim of a sharp structural 'if and only if' threshold is not supported by the lower-bound results as written: Lemma 8.1 is not proved in its stated regime, and Lemma 8.11 addresses the residual norm rather than the trimmed-k sum. The conditional algorithmic results remain significant, but the paper's advertised characterization is currently an overstatement.

major comments (6)
  1. [§8.1.1, Lemma 8.1 and Corollary 8.5; abstract and §1.1] The sharp-threshold claim is not established. Theorem 4.1 gives poly(log n / eps) space when a_k^2 >= (eps/log n)^c ||x_-k||_2^2 / k (Eq. 2). Lemma 8.1 claims Omega(eps^{-2} n/k) space when a_k^2 <= c (k/n) ||x_-k||_2^2 / k, but the 2-SUM construction in its proof does not satisfy this premise: in the constructed vector A, all nonzero entries are k/2 or k and the total number of nonzero entries is at most (2-c_0)k for the constant fraction c_0 of intersecting pairs, so U - k is O(k), and a_k^2 <= c (k/n) ||A_-k||_2^2 / k would force n = O(U - k), contradicting k <= 0.1n. Only the padded Corollary 8.5, with k/n^c in place of k/n for c < 1, follows; that condition is far weaker than the upper-bound condition. The gap between (eps/log n)^c * tail/k and c' (k/n^c) * tail/k is uncharacterized, so the 'if and only if' language in the abstract and Section 1.1 is unsupported.
  2. [§8.2, Lemma 8.11] The lower bound stated for the trimmed-k moment is actually about the residual norm. Lemma 8.11 concerns ||x_-k||_p^p, i.e., the vector after deleting only the top k coordinates, whereas Section 5 defines the trimmed-k statistic as sum_{i=k}^{n-k} |a_i|^p after deleting both the largest and smallest k coordinates. In the Gap-Hamming reduction with Delta(a,b)=k and Delta=k+eps k, the vector x - y has m = k or k + eps k nonzero entries of magnitude B; since m < 2k for eps < 1, deleting the top k and bottom k entries leaves the zero vector in both cases. The construction therefore cannot distinguish the two cases for the trimmed-k sum, and the claimed unavoidability of the additive term eps k |a_{k-eps k}|^p is not proven.
  3. [§4, Lemma 4.6 and Eq. (3)] The proof of Lemma 4.6 relies on the inequality v >= a_k in Lemma 4.3 (Eq. 3), but the premise zeta(1+eps)^{t-j} >= |a_k| together with v = zeta(1+eps)^{t-j-1} only implies v >= |a_k|/(1+eps). This introduces a (1+eps)^{p-2} factor into the bound s_j v^2 >= (eps/log n)^{c+2} ||x_-k||_2^2 and propagates to the tail-error estimate in Lemma 4.6. The gap is a constant factor that can likely be absorbed by adjusting the exponent c, but as written the derivation does not yield the stated lemma, and Theorem 4.1 depends on it.
  4. [§4, Remark 4.1] Remark 4.1 asserts that condition (2) is always met when k >= polylog n. This is false. For a vector with k - 1 coordinates equal to M and n - k + 1 coordinates equal to 1, one has a_k = 1 and ||x_-k||_2^2 is about n, so (2) becomes 1 >= (eps/log n)^c (n - k)/k, which fails when n/k is super-polylogarithmic, e.g., when k = polylog n. The correct moderately-large regime appears to be k >= n/polylog n, as stated in the introduction; the remark as written contradicts that and should be corrected.
  5. [§7.2.2, Corollary 7.6 and §1.1] The advertised improvement for the h-index over Govindan, Monemizadeh, and Muthukrishnan is stated unconditionally, for example 'when h = n^{1/3} ... our algorithm achieves O(poly(log n/eps)) bits', but Corollary 7.6 requires a_{(1+eps)k}^2 >= (eps/log n)^c ||x_{-(1+eps)k}||_2^2 / k. For a natural h-index vector in which the top h coordinates equal h and the remaining coordinates equal h - 1, this condition becomes h^2 >= (eps/log n)^c * n h, which fails when h = n^{1/3}. The h-index comparison is therefore only valid under an additional heavy-tail assumption that is not part of the h-index definition, and the claimed improvement should be stated conditionally.
  6. [§8.1.2, Lemma 8.6] The set-disjointness reduction assumes that in the disjoint case the vector x is (1,1,...,1) and that ||x_-k||_2^2 = n - k. This requires that the players' sets cover the entire universe [m], which is not part of the k-player set-disjointness promise in Lemma 8.7. When some coordinates are covered by no player, the top-k entries can include zeros and the claimed values of a_k and ||x_-k||_2^2 are not correct; the Omega(n/k^3) bound is therefore not derived as written.
minor comments (5)
  1. [§4, Algorithm 1 line 6] The pseudocode uses 'poly(eps/L) heavy hitters', which is inconsistent with the (log n/eps)^{c+9} bucket count used in Lemma 4.6 and in the surrounding text; the notation should be unified.
  2. [§8.1.2 and §6] There are typos: 'k-plyaer' should be 'k-player' in Section 8.1.2, and 'Holder' should be 'Hölder' in Section 6.
  3. [§4, Lemma 4.8] The proof says 'There are log m / O(eps) level sets' but then uses log^2 n in the bound; since m = poly(n), this is O(log n/eps), and the denominator should be written consistently.
  4. [§9, Figure 1] The text refers to Figure 1, but the figure appears not to be included in the manuscript text; ensure the figure is present in the submitted version.
  5. [§2, Definition 2.1] In Definition 2.1, the heavy-hitter structure is defined with a parameter k that is unrelated to the k in the main theorems; the reader must guess which k is meant. Clarify by using a different parameter name, such as t.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the top-k F_p estimator is derived from standard Count-Sketch and Chernoff facts under an explicit input condition, and no fitted parameter is renamed as a prediction.

full rationale

The derivation chain in Theorem 4.1 is self-contained: Algorithm 1 estimates level-set sizes from sub-sampled Count-Sketch heavy hitters, and Lemmas 4.3 through 4.8 prove the estimates are (1±ε)-accurate assuming condition (2). No parameter is fitted to the target quantity; condition (2) is an input assumption of the theorem, not an output that the algorithm is then claimed to predict. The lower bound in Lemma 8.1 reduces from the 2-SUM communication problem of [12], a published lower-bound statement whose assumptions do not include the top-k F_p moment; although [12] shares authors with this paper, it is external evidence rather than an unverified self-citation. The citations to [36] in Remark 4.2 are minor optimization asides and are not load-bearing for the main theorems. The abstract's claim of a sharp 'if and only if' threshold is not actually established by the formal statements, since the upper-bound condition and the lower-bound condition leave an uncharacterized gap, but that is a correctness or overstatement concern, not a circularity in which the claimed result is equivalent to its input by construction. No circular step was found.

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

The central upper bound rests on a chain of standard tools (Count-Sketch, Chernoff, subsampling with level sets) plus a new residual-norm comparison. No parameters are fit to data. The lower bounds rely on published communication complexity results, including one from the authors' own prior work [12], but used as black boxes.

assumptions (8)
  • standard math Count-Sketch tail bound: with O(log n) repetitions and B buckets, each coordinate estimate has error O(||x_{-B}||_2 / sqrt(B)) with high probability.
    Invoked in Section 2 and used throughout Lemmas 4.6, 5.6, and 6.3 as the core heavy-hitter tool.
  • standard math Chernoff bound for sums of independent Bernoulli subsampling indicators.
    Used in Lemmas 4.4, 4.5, and 4.6 to control the number of survivors in a level set.
  • standard math 2-SUM communication lower bound of Cheng et al. [12]: Omega(tL/alpha) bits needed.
    Used as a black box in Lemma 8.1 to prove the Omega(eps^{-2} n/k) lower bound for top-k F_p.
  • standard math Gap-Hamming one-way communication lower bound Omega(eps^{-2} log n log(1/delta)) [28].
    Used in Lemma 8.11 for the additive-error lower bound.
  • standard math k-player set disjointness lower bound Omega(m/k) [22,27,30].
    Used in Lemma 8.6 for the Omega(n/k^3) lower bound.
  • standard math Holder's inequality ||u||_2 * n^{-(1/2-1/p)} <= ||u||_p for p > 2.
    Used in Section 6 to convert ell_2 heavy hitter guarantees to ell_p tail bounds.
  • domain assumption Turnstile stream model: updates are +-1 to coordinates, stream length poly(n), each coordinate bounded by m = poly(n).
    Stated in Section 2; bounds the number of level sets to log m / (2 eps).
  • domain assumption Hash functions are fully random; derandomization via Nisan's PRG adds a poly(log n) factor.
    Stated in Section 2 under 'Derandomization'.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On Sketching Trimmed Statistics." pith.science (2026). https://pith.science/paper/Z3NCNIR2

@misc{pith2026250607342,
  author       = {Pith},
  title        = {Pith review of: On Sketching Trimmed Statistics},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Z3NCNIR2}},
  note         = {Machine review of arXiv:2506.07342}
}
abstract

We study sketching trimmed statistics of a frequency vector, including the $F_p$ moment of the top-$k$ coordinates and of the trimmed-$k$ vector. Despite their natural role in robust analytics, this is the first time these problems have been studied in any sublinear space setting. For $p \in [0,2]$, we obtain $poly(\log n/\varepsilon)$-space algorithms for both tasks when $k$ is moderately large, and for general $k$ we identify a sharp structural threshold that characterizes exactly when sublinear space is possible: in particular, it is actually determined by the ratio between $a_k^2$ and $\|x_{-k}\|_2^2/k$. We extend these results to $p > 2$ and present several applications including algorithms for thresholded $F_p$ estimation and generalized impact indices. Notably, we improve the space bounds of Govindan, Monemizadeh, and Muthukrishnan (PODS 2017) for computing the $h$-index.

Figures

Figures reproduced from arXiv: 2506.07342 by the authors.

Figure 1
Figure 1. Number of Buckets vs Error (Synthetic, AOL, CAIDA respectively). [PITH_FULL_IMAGE:figures/full_fig_p023_1.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

48 extracted references · 32 canonical work pages

  1. [12]

    Woodruff, and Jason Zhang

    Yu Cheng, Max Li, Honghao Lin, Zi-Yi Tai, David P. Woodruff, and Jason Zhang. 2024. Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut.Proc. ACM Manag. Data2, 2 (2024), 85. doi:10.1145/3651148

    work page doi:10.1145/3651148 2024

  2. [36]

    Woodruff

    Honghao Lin, Hoai-An Nguyen, William Swartworth, and David P. Woodruff. 2026. Unbiased Insights: Optimal Streaming Algorithms forℓ𝑝 Sampling, the Forget Model, and Beyond. InSymposium on Principles of Database Systems 2026

    work page 2026

  3. [1]

    Noga Alon, Yossi Matias, and Mario Szegedy. 1999. The Space Complexity of Approximating the Frequency Moments. J. Comput. Syst. Sci.58, 1 (1999), 137–147. doi:10.1006/JCSS.1997.1545

    arXiv 1999

  4. [2]

    Sergio Alonso, Francisco Javier Cabrerizo, Enrique Herrera-Viedma, and Francisco Herrera. 2009. h-Index: A Review Focused in its Variants, Computation and Standardization for Different Scientific Fields.J. Informetrics3, 4 (2009), 273–289. doi:10.1016/J.JOI.2009.04.001 Proc. ACM Manag. Data, Vol. 4, No. 2 (PODS), Article 111. Publication date: May 2026. O...

    work page doi:10.1016/j.joi.2009.04.001 2009

  5. [3]

    Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak. 2011. Streaming Algorithms via Precision Sampling. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. IEEE, 363–372

    work page 2011

  6. [4]

    Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. 2004. An Information Statistics Approach to Data Stream and Communication Complexity.J. Comput. System Sci.68, 4 (2004), 702–732. doi:10.1016/j.jcss.2003.11.006

    doi:10.1016/j.jcss.2003.11.006 2004

  7. [5]

    Woodruff

    Arnab Bhattacharyya, Palash Dey, and David P. Woodruff. 2016. An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems. InProceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016, Tova Milo and Wang-Chiew Tan (Eds.). ACM, 385–400. doi:...

    arXiv 2016

  8. [6]

    Mark Braverman and Or Zamir. 2024. Optimality of Frequency Moment Estimation.CoRRabs/2411.02148 (2024). arXiv:2411.02148 doi:10.48550/ARXIV.2411.02148

    work page Pith review arXiv doi:10.48550/arxiv.2411.02148 2024

Show all 48 references
  1. [7]

    Chestnut, Nikita Ivkin, Jelani Nelson, Zhengyu Wang, and David P

    Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, Jelani Nelson, Zhengyu Wang, and David P. Woodruff. 2017. BPTree: Anℓ2-Heavy Hitters Algorithm Using Constant Memory. InProceedings of the 36th ACM SIGMOD-SIGACT- SIGAI Symposium on Principles of Database Systems, PODS 201...

    2017

  2. [8]

    Chestnut, Nikita Ivkin, and David P

    Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, and David P. Woodruff. 2016. Beating CountSketch for Heavy Hitters in Insertion Streams. InProceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, Daniel...

    2016

  3. [9]

    2008–ongoing

    Center for Applied Internet Data Analysis (CAIDA). 2008–ongoing. The CAIDA UCSD IPv4 Routed /24 DNS Names Dataset - May 6, 2025. https://www.caida.org/catalog/datasets/ipv4_dnsnames_dataset/. Accessed: 2025-05-06

    2008

  4. [10]

    Amit Chakrabarti, Subhash Khot, and Xiaodong Sun. 2003. Near-Optimal Lower Bounds on the Multi-Party Communi- cation Complexity of Set Disjointness. In18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 7-10 July 2003, Aarhus, Denmark. IEEE Computer Soci...

    2003 arXiv

  5. [11]

    Chen, and Martin Farach-Colton

    Moses Charikar, Kevin C. Chen, and Martin Farach-Colton. 2002. Finding Frequent Items in Data Streams. InAutomata, Languages and Programming, 29th International Colloquium, ICALP 2002, Malaga, Spain, July 8-13, 2002, Proceedings (Lecture Notes in Computer Science, Vol. 2380), ...

    2002 doi

  6. [13]

    Clarkson and David P

    Kenneth L. Clarkson and David P. Woodruff. 2015. Sketching for M-Estimators: A Unified Approach to Robust Regression. InProceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, Piotr Indyk (Ed.). SIAM, ...

    2015 doi

  7. [14]

    Edith Cohen and Haim Kaplan. 2007. Bottom-k sketches: better and more efficient estimation of aggregates. In Proceedings of the 2007 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2007, San Diego, California, USA, June 12-16...

    2007

  8. [15]

    Majid Daliri, Juliana Freire, Christopher Musco, Aécio S. R. Santos, and Haoxiang Zhang. 2024. Sampling Methods for Inner Product Sketching.Proc. VLDB Endow.17, 9 (2024), 2185–2197

    2024

  9. [16]

    Elbert Du, Michael Mitzenmacher, David Woodruff, and Guang Yang. 2023. Separating𝑘-Player from𝑡-Player One-Way Communication, with Applications to Data Streams.Theory of Computing19, 10 (2023), 1–44. doi:10.4086/toc.2023. v019a010

    2023 doi

  10. [17]

    Seshadhri

    Talya Eden, Shweta Jain, Ali Pinar, Dana Ron, and C. Seshadhri. 2018. Provable and Practical Approximations for the Degree Distribution using Sublinear Graph Samples. InProceedings of the 2018 World Wide Web Conference on World Wide Web, WWW 2018, Lyon, France, April 23-27, 20...

    2018

  11. [18]

    Leo Egghe. 2006. Theory and Practise of theg-index.Scientometrics69, 1 (2006), 131–152. doi:10.1007/S11192-006-0144-7

    2006 doi

  12. [19]

    Gereon Frahling, Piotr Indyk, and Christian Sohler. 2008. Sampling in Dynamic Data Streams and Applications. Internat. J. Comput. Geom. Appl.18, 1-2 (2008), 3–28. doi:10.1142/S0218195908002520

    2008 doi

  13. [20]

    Sumit Ganguly. 2011. Polynomial Estimators for High Frequency Moments.CoRRabs/1104.4552 (2011)

    2011 arXiv

  14. [21]

    Muthukrishnan

    Priya Govindan, Morteza Monemizadeh, and S. Muthukrishnan. 2017. Streaming Algorithms for Measuring H-Impact. InProceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017, Chicago, IL, USA, May 14-19, 2017, Emanuel Sallinger, Jan Van...

    2017

  15. [22]

    André Gronemeier. 2009. Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Complexity of the AND-Function and Disjointness. In26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, February 26-28, 2009, Freiburg, Germany, Proce...

    2009

  16. [23]

    Jorge E. Hirsch. 2005. An Index to Quantify an Individual’s Scientific Research Output.Proc. Natl. Acad. Sci. USA102, 46 (2005), 16569–16572. doi:10.1073/PNAS.0507655102

    2005 doi

  17. [24]

    Piotr Indyk. 2006. Stable Distributions, Pseudorandom Generators, Embeddings, and Data Stream Computation.J. ACM53, 3 (2006), 307–323. doi:10.1145/1147954.1147955

    2006

  18. [25]

    Piotr Indyk and David Woodruff. 2005. Optimal Approximations of the Frequency Moments of Data Streams. In STOC’05: Proceedings of the 37th Annual ACM Symposium on Theory of Computing. ACM, New York, 202–208. doi:10. 1145/1060590.1060621

    2005

  19. [26]

    Rajesh Jayaram and David Woodruff. 2021. Perfect 𝐿𝑝 Sampling in a Data Stream.SIAM J. Comput.50, 2 (2021), 382–439. doi:10.1137/18M1229912

    2021 doi

  20. [27]

    T. S. Jayram. 2009. Hellinger Strikes Back: A Note on the Multi-Party Information Complexity of AND. InApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 200...

    2009 doi

  21. [28]

    T. S. Jayram and David P. Woodruff. 2011. Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Sub-Constant Error. InProceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January...

    2011

  22. [29]

    Hossein Jowhari, Mert Saglam, and Gábor Tardos. 2011. Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems. InProceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2011, June 12-16, 2011, Athens, Greece,...

    2011

  23. [30]

    Woodruff

    Akshay Kamath, Eric Price, and David P. Woodruff. 2021. A Simple Proof of a New Set Disjointness with Applications to Data Streams. In36th Computational Complexity Conference, CCC 2021, July 20-23, 2021, Toronto, Ontario, Canada (Virtual Conference) (LIPIcs, Vol. 200), Valenti...

    2021 doi

  24. [31]

    Kane, Jelani Nelson, and David P

    Daniel M. Kane, Jelani Nelson, and David P. Woodruff. 2010. On the Exact Space Complexity of Sketching and Streaming Small Norms. InProceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, Moses Chari...

    2010 doi

  25. [32]

    Kane, Jelani Nelson, and David P

    Daniel M. Kane, Jelani Nelson, and David P. Woodruff. 2010. An Optimal Algorithm for the Distinct Elements Problem. InProceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2010, June 6-11, 2010, Indianapolis, Indiana, USA, J...

    2010

  26. [33]

    Woodruff, and Mobin Yahyazadeh

    Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P. Woodruff, and Mobin Yahyazadeh. 2017. Optimal Lower Bounds for Universal Relation, and for Samplers and Finding Duplicates in Streams. In58th IEEE Annual Symposium on Foundations of Computer Science, FOCS ...

    2017 doi

  27. [34]

    Woodruff

    Yi Li, Honghao Lin, and David P. Woodruff. 2024. Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms. InThe Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net. https://openreview.net/...

    2024

  28. [35]

    Woodruff

    Yi Li and David P. Woodruff. 2013. A Tight Lower Bound for High Frequency Moment Estimation with Small Error. InApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX 2013, and 17th International Workshop, ...

    2013

  29. [37]

    Eugene Stanley

    Linyuan Lü, Tao Zhou, Qian-Ming Zhang, and H. Eugene Stanley. 2016. The H-Index of a Network Node and its Relation to Degree and Coreness.Nature Communications7, 1 (April 2016), 1–7. doi:10.1038/ncomms10168

    2016 doi

  30. [38]

    Woodruff

    Morteza Monemizadeh and David P. Woodruff. 2010. 1-Pass Relative-Error L p-Sampling with Applications. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, Moses Charikar (Ed.). SIAM, 1143–1160...

    2010 doi

  31. [39]

    Jelani Nelson and Huacheng Yu. 2022. Optimal Bounds for Approximate Counting. InPODS ’22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022, Leonid Libkin and Pablo Barceló (Eds.). ACM, 119–127. doi:10.1145/3517804.3526225 Proc. ACM Mana...

    2022

  32. [40]

    Noam Nisan. 1992. Pseudorandom Generators for Space-Bounded Computation.Combinatorica12, 4 (1992), 449–461. doi:10.1007/BF01305237

    1992 doi

  33. [41]

    Greg Pass, Abdur Chowdhury, and Cayley Torgeson. 2006. A Picture of Search. InProceedings of the 1st International Conference on Scalable Information Systems, Infoscale 2006, Hong Kong, May 30-June 1, 2006 (ACM International Conference Proceeding Series, Vol. 152), Xiaohua Jia...

    2006

  34. [42]

    Fabián Riquelme. 2015. Measuring User Influence on Twitter: A survey.CoRRabs/1508.07951 (2015). arXiv:1508.07951 http://arxiv.org/abs/1508.07951

    2015 arXiv

  35. [43]

    Jake Roth and Ying Cui. 2023. On𝑂(𝑛) Algorithms for Projection onto the Top-𝑘-sum Constraint.CoRRabs/2310.07224 (2023). arXiv:2310.07224 doi:10.48550/ARXIV.2310.07224

    2023 doi

  36. [44]

    Seshadhri, and Ali Pinar

    Ahmet Erdem Sariyüce, C. Seshadhri, and Ali Pinar. 2018. Local Algorithms for Hierarchical Dense Subgraph Discovery. Proc. VLDB Endow.12, 1 (2018), 43–56. doi:10.14778/3275536.3275540

    2018

  37. [45]

    David Woodruff. 2004. Optimal Space Lower Bounds for all Frequency Moments. InProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 167–175

    2004

  38. [46]

    Woodruff

    David P. Woodruff. 2016. New Algorithms for Heavy Hitters in Data Streams. In19th International Conference on Database Theory, ICDT 2016, Bordeaux, France, March 15-18, 2016 (LIPIcs, Vol. 48), Wim Martens and Thomas Zeume (Eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informat...

    2016 doi

  39. [47]

    Woodruff, Shenghao Xie, and Samson Zhou

    David P. Woodruff, Shenghao Xie, and Samson Zhou. 2025. Perfect Sampling in Turnstile Streams Beyond Small Moments. arXiv:2504.07237 [cs.DS] https://arxiv.org/abs/2504.07237

    2025 arXiv

  40. [48]

    Woodruff and Qin Zhang

    David P. Woodruff and Qin Zhang. 2014. An Optimal Lower Bound for Distinct Elements in the Message Passing Model. InProceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 718–733. doi:10.1137/1.9781611973402.54 Received December 2025; ...

    2014 doi

Pith tools

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