Pith. sign in

REVIEW 2 major objections 4 minor 37 references

Tight Bounds for Low-Error Frequency Moment Estimation and the Power of Multiple Passes

T0 review · 2 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash

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

Pith's one-line read The paper proves that (1±ε)-estimating F2 of an n-element stream takes Θ(n log(1/(ε²n))) bits for ε < 1/√n, completing the one-pass space curve.

desk verdict The F2 low-error bound and the communication characterization look solid and significant, but the two-pass exact-histogram algorithm has a real gap—Newman's reduction doesn't make the hash evaluable—so Theorem 3 needs revision. read the letter →

arxiv 2509.07599 v1 pith:QZWSPQ7U submitted 2025-09-09 cs.DS

Naomi Green-Maimon , Or Zamir This is my paper · ORCID
classification cs.DS MSC 68Q1768Q2568W2068W27
keywords frequencymomentsF2estimationstreamingalgorithmscommunicationcomplexityapproximatesetintersectionmulti-passspacedatastreams
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 closes the last open range in the one-pass space complexity of estimating the second frequency moment F2 of a data stream. For relative error ε smaller than 1/√n, it proves that any one-pass algorithm needs Θ(n log(1/(ε²n))) bits, and it gives a simple hashing-based estimator matching this bound. Combined with the previously known tight bound for larger ε, the one-pass answer is now settled for every error level. The proof runs through a full characterization of the one-way communication complexity of approximating set intersection sizes, exposing a Θ(n log(1/(ε²n))) versus Θ(n) gap between one-way and two-way protocols in this low-error regime. Motivated by that gap, the paper also gives a two-pass algorithm that computes the exact stream histogram in O(n log log n) bits, the first asymptotic separation between one-pass and constant-pass space for small frequency-moment estimation.

What carries the argument

Two mechanisms carry the results. For the lower bound, a block-uniform distribution builds exponentially many n-element sets whose pairwise intersections are at most n/400; any small family of Bob's sets that distinguishes every such pair forces Alice's one-way message to encode her entire input, yielding the extra log factor. For the multipass algorithm, the central object is the discrepancy polynomial Δ(z) = TrueSum(z) − HistSum(z), whose coefficients measure how far the fingerprint-based histogram over- or under-counts each element. After evaluating this polynomial at random field elements in the second pass, only O(n/(log n)^6) nonzero coefficients survive with high probability, so the a

What would settle it

Run the Section 6.2 algorithm on a stream where two distinct elements in the same bucket collide under the fingerprint function, execute Pass 1 to store only (fingerprint, counter) pairs, then perform Pass 2 and attempt the Output correction: if the algorithm cannot determine which stored fingerprint entry to decrement for one element and which to increment for the other without knowing the elements by name, the claimed O(n log log n) two-pass histogram result fails on that instance.

Watch

Extended reading notes

Core claim

The core claim is Theorem 1: for 1/n² ≤ ε ≤ 1/√n, any (1±ε)-estimator of the second frequency moment of an n-element stream uses Θ(n log(1/(ε²n))) bits of space, assuming a sufficiently large universe. At the communication level, the paper proves that one-way protocols approximating |A∩B| up to additive error εn require Θ(n log(1/(ε²n))) bits when ε < 1/√n, while two-way protocols require only Θ(n) bits; for ε ≥ 1/√n both models require Θ(1/ε² + log n). This completes the characterization of the Approximate Set Intersection problem and, by reduction, the one-pass F2 space complexity. The paper further claims a two-pass streaming algorithm that computes the exact histogram of a stream with hi

Load-bearing premise

The two-pass exact-histogram algorithm assumes that after recovering the discrepancy polynomial, the algorithm can tell which original element each nonzero correction applies to, even though the stored fingerprints and counters do not identify elements by name or by hash value.

Editorial extensions

If this is right

  • The one-pass space complexity of F2 estimation is now known up to constants for every error ε: Θ(n log(1/(ε²n))) below 1/√n and Θ(log(ε²n)/ε²) above it.
  • Any one-way protocol for approximate set intersection at ε < 1/√n must use Θ(n log(1/(ε²n))) bits, so the classical O(n)-bit two-way exact-intersection protocol cannot be simulated one-way without this overhead.
  • Exact histograms, and hence exact F2, can be computed in two passes using o(n log n) memory, whereas one-pass small-error F2 estimation needs Θ(n log n) bits; this is the first one-pass versus O(1)-pass separation for small frequency moments.
  • For exact histogram computation with r passes, the paper establishes that Θ(n log^{(Θ(r))} n) bits are both necessary and sufficient, pinning down the pass-memory tradeoff within iterated logarithms.
  • The one-way/two-way communication gap transfers to streaming: the Θ(n log(1/(ε²n))) F2 lower bound is inherently a one-pass phenomenon and does not rule out faster multi-pass algorithms in the low-error regime.

Reading between the lines

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

  • The two-pass histogram algorithm's correction step presupposes a way to map each recovered discrepancy coefficient back to a specific stored fingerprint entry; since the O(n log log n)-bit histograms store fingerprints and counters but not element identities or hash values, executing that step may require a third pass or extra identity storage unless additional structure is supplied.
  • The discrepancy-polynomial recovery idea could plausibly extend to other summary problems, such as exact heavy-hitter recovery or estimating other low-order frequency moments, though the paper does not make that claim.
  • The sharp phase transition at ε = 1/√n suggests the high-error regime might behave differently for multi-pass algorithms; the paper leaves the existence of a one-pass versus constant-pass separation there as an open question.
  • The sparse-recovery step as written enumerates a candidate family of size up to 2^n, so the two-pass result is a space bound; standard polynomial sparse-interpolation techniques may make the algorithm time-efficient without changing its memory profile.
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

2 major / 4 minor

Summary. The paper studies the one-pass streaming space complexity of (1±ε)-estimating the second frequency moment F2 in the low-error regime ε < 1/√n. It proves a tight Θ(n log(1/(ε^2 n))) bound for 1/n^2 ≤ ε ≤ 1/√n, completing the characterization started by Braverman and Zamir. The lower bound is obtained via a new communication-complexity result for Approximate Set Intersection: in the one-way model the complexity is Θ(n log(2/(ε^2 n))) for ε < 1/√n and Θ(1/ε^2 + log n) for ε ≥ 1/√n, while the two-way complexity is Θ(n) in the low-error regime. The upper bound for F2 uses hashing to a domain of size Θ(1/ε^2) and subtracts the expected number of hash collisions. The paper further claims a two-pass streaming algorithm that computes an exact histogram in O(n log log n) bits, based on sparse recovery of a discrepancy polynomial, and an r-pass generalization with Θ(n log^{(r)} n) memory.

Significance. If the main theorem holds, it completes the tight characterization of one-pass F2 estimation for all error parameters, resolving a central open gap. The lower-bound framework (Sections 3.1–3.2) is coherent and the F2 upper bound (Section 4.1) is elegant and parameter-clean; the design/union-bound arguments in Lemmas 3.5–3.8 are careful and mostly sound. The claimed separation between one-pass and constant-pass space for F2 would also be a notable contribution. However, the two-pass and r-pass histogram algorithms currently contain a load-bearing gap in the representation of the random hash and an incorrect correction rule, so this part of the paper is not established as written.

major comments (2)
  1. [§6.2, 'Representing the hash h'] Lemma 6.5 uses h:U→F_q with q=3^n and applies Schwartz-Zippel to a family D of size 2^n. A fully random h requires |U|log q = Ω(n^2) bits to store; the cited Newman reduction supplies only an index of a random string, not an evaluable hash function, and the selected string may be exponentially long. With only O(log n)-wise independence, a non-zero linear polynomial can vanish on all hash values (e.g., coefficients forming a low-order moment) with probability 1, so the union bound over D fails. Storing an s-wise independent hash with s=6n/(log n)^5 costs s log q = Ω(n^2/log^5 n) bits, exceeding the claimed O(n log log n). Thus the two-pass algorithm is not implementable in the stated space and Lemma 6.5 is not proved. The same Newman appeal appears in Appendix A.
  2. [§6.2, 'Output' paragraph] The correction rule is inconsistent with the sign convention Δ=TrueSum−HistSum. For a collision group with frequencies (3,5,7) under one fingerprint, Δ has positive coefficients 5 and 7 at non-representative elements and one negative coefficient −12 at the representative. The rule subtracts 5 and 7 from the single existing entry (leaving 3) and creates one new entry with counter 12, yielding frequencies {3,12} instead of {3,5,7}. To recover the histogram one must create a new entry for each positive coefficient and reduce the representative entry by their total; as written the proof of exactness fails. Additionally, the newly created entries use arbitrary 'unused fingerprints' not attached to actual element names, so the output is not an exact histogram in the standard per-item sense.
minor comments (4)
  1. [Theorem 1] The statement Θ(n log(1/(ε^2 n))) gives zero at the endpoint ε=1/√n, where the correct complexity is Θ(n). It should be Θ(n(1+|log(ε^2 n)|)) or Θ(n log(2/(ε^2 n))) to cover the endpoint and match the abstract.
  2. [Lemma 3.6] In the Berry–Esseen step, x* is in (−0.853,−0.603) and Φ is decreasing, so the inequality should be Φ(x*) ≤ Φ(−0.603), not ≥. Replacing 0.2736 by Φ(−0.853)≈0.197 still yields a positive constant c1, so the qualitative claim is unaffected.
  3. [Lemmas 6.2 and 6.5] The definitions of TrueSum and HistSum use the ambiguous notation Σ_{i=1}^{|U|} z_{x_i}. They should be defined explicitly as Σ_{x∈U} f_x z_x and Σ_{x∈U} f_x z_{first(x)}, with f_x the frequency of x.
  4. [§6.2] The discrepancy polynomial Δ is linear, not 'multi-linear' as stated; the family D in Definition 6.6 should likewise be described as a family of linear polynomials.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity; the lone self-citation ([BZ25]) is contextual and non-load-bearing.

full rationale

The paper's central results are derived from independent lower-bound machinery (information-theoretic design construction following DKS12, Yao minimax, Fano, Berry-Esseen, FKG), external communication lower bounds (Chakrabarti-Regev for Gap Hamming), and standard algorithmic techniques (Chernoff limited-independence bounds, Schwartz-Zippel, Newman's theorem). The low-error F2 upper bound (Algorithm A) is an explicit unbiased estimator with variance bound, not a fit renamed as prediction. The remaining tightness in the small-error regime does not invoke the authors' own prior [BZ25] result except as context for the complementary high-error regime; no equation or parameter from [BZ25] is used in the proofs. The two-pass histogram algorithm's correctness relies on a Schwartz-Zippel argument over a brute-force enumeration of a hypothesis family D; the family is defined from the discrepancy polynomial, not from the algorithm's own output, so there is no self-definitional reduction. Potential concerns about the implementability of the hash function h (e.g., whether Newman's reduction yields an evaluable function in streaming) are correctness/technical issues rather than circularity: they do not make any claimed conclusion equal to an input by construction. Accordingly, the derivation chain is self-contained with respect to circularity.

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

The paper is a pure theory preprint; no empirical parameters are fitted except universal constants chosen in proofs. The axioms listed are the standard mathematical tools and the domain-specific assumptions (large universe, hash families, randomness reduction) on which the arguments depend. The two-pass algorithm's hidden assumption about identity availability is not listed as an axiom because it is not stated; it is the main gap.

assumptions (6)
  • domain assumption The universe size |U| is polynomial in n, and can be assumed |U| ≤ O(n^2) by hashing.
    Section 1, paragraph 1. The entire analysis assumes universe poly(n), and the lower bounds require a sufficiently large universe.
  • standard math Existence of k-wise independent hash functions with O(log n) seed for k up to 6 log n.
    Used throughout: 4-wise in Section 4, 6 log n-wise in Section 6. This is standard in streaming literature.
  • standard math Chernoff bounds for limited independence (Schmidt-Siegel-Srinivasan) apply to bucket load analysis.
    Lemma 6.3 uses the limited-independence Chernoff bound to show each bucket contains at most O(log n) distinct elements.
  • standard math Berry-Esseen inequality with Shevtsova's constant applies to the sum of independent Bernoulli variables.
    Lemma 3.6, Step 2. Used to bound Pr[Z'_diff ≤ μ_M - 0.603√μ_M]. The proof has a minor numerical typo but the qualitative bound holds for large n.
  • ad hoc to paper The probabilistic method yields a design X of size exp(c α n ln n) and a distinguishing family Y of size k α n ln n.
    Lemmas 3.5 and 3.7 construct these families. This is the core of the communication lower bound; the construction is self-contained though non-explicit.
  • domain assumption Newman's public-to-private randomness reduction applies to streaming algorithms with O(log n) additional bits.
    Section 6.2, 'Representing the hash h'. The paper asserts this applies to streaming; it is standard in communication complexity but its streaming application requires the number of inputs N = |U|^n and a seed of O(log log N) bits. This is plausible but not fully proven in the text.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Tight Bounds for Low-Error Frequency Moment Estimation and the Power of Multiple Passes." pith.science (2026). https://pith.science/paper/QZWSPQ7U

@misc{pith2026250907599,
  author       = {Pith},
  title        = {Pith review of: Tight Bounds for Low-Error Frequency Moment Estimation and the Power of Multiple Passes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QZWSPQ7U}},
  note         = {Machine review of arXiv:2509.07599}
}
abstract

Estimating the second frequency moment $F_2$ of a data stream up to a $(1 \pm \varepsilon)$ factor is a central problem in the streaming literature. For errors $\varepsilon > \Omega(1/\sqrt{n})$, the tight bound $\Theta\left(\log(\varepsilon^2 n)/\varepsilon^2\right)$ was recently established by Braverman and Zamir. In this work, we complete the picture by resolving the remaining regime of small error, $\varepsilon < 1/\sqrt{n}$, showing that the optimal space complexity is $\Theta\left( \min\left(n, \frac{1}{\varepsilon^2} \right) \cdot \left(1 + \left| \log(\varepsilon^2 n) \right| \right) \right)$ bits for all $\varepsilon \geq 1/n^2$, assuming a sufficiently large universe. This closes the gap between the best known $\Omega(n)$ lower bound and the straightforward $O(n \log n)$ upper bound in that range, and shows that essentially storing the entire stream is necessary for high-precision estimation. To derive this bound, we fully characterize the two-party communication complexity of estimating the size of a set intersection up to an arbitrary additive error $\varepsilon n$. In particular, we prove a tight $\Omega(n \log n)$ lower bound for one-way communication protocols when $\varepsilon < n^{-1/2-\Omega(1)}$, in contrast to classical $O(n)$-bit protocols that use two-way communication. Motivated by this separation, we present a two-pass streaming algorithm that computes the exact histogram of a stream with high probability using only $O(n \log \log n)$ bits of space, in contrast to the $\Theta(n \log n)$ bits required in one pass even to approximate $F_2$ with small error. This yields the first asymptotic separation between one-pass and $O(1)$-passes space complexity for small frequency moment estimation.

Figures

Figures reproduced from arXiv: 2509.07599 by the authors.

Figure 1
Figure 1. The optimal space complexity of second moment estimation for all values of [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Complexity of Approximate Set Intersection and [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

37 extracted references · 34 canonical work pages

  1. [1]

    Tracking join and self-join sizes in limited storage

    Noga Alon, Phillip B Gibbons, Yossi Matias, and Mario Szegedy. Tracking join and self-join sizes in limited storage. In Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , pages 10--20, 1999

    work page 1999

  2. [2]

    Streaming algorithms via precision sampling

    Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak. Streaming algorithms via precision sampling. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science , pages 363--372. IEEE, 2011

    work page 2011

  3. [3]

    The space complexity of approximating the frequency moments

    Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing , pages 20--29, 1996

    work page 1996

  4. [4]

    High frequency moments via max-stability

    Alexandr Andoni. High frequency moments via max-stability. In 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) , pages 6364--6368. IEEE, 2017

    work page 2017

  5. [5]

    Woodruff, and Grigory Yaroslavtsev

    Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, and Grigory Yaroslavtsev. Beyond set disjointness: the communication complexity of finding the intersection. In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing , PODC '14, page 106–113, New York, NY, USA, 2014. Association for Computing Machinery

    work page 2014

  6. [6]

    Simpler algorithm for estimating frequency moments of data streams

    Lakshminath Bhuvanagiri, Sumit Ganguly, Deepanjan Kesh, and Chandan Saha. Simpler algorithm for estimating frequency moments of data streams. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm , pages 708--713, 2006

    work page 2006

  7. [7]

    Recursive sketching for frequency moments

    Vladimir Braverman and Rafail Ostrovsky. Recursive sketching for frequency moments. arXiv preprint arXiv:1011.2571 , 2010

    arXiv 2010

  8. [8]

    A deterministic algorithm for sparse multivariate polynomial interpolation

    Michael Ben-Or and Prasoon Tiwari. A deterministic algorithm for sparse multivariate polynomial interpolation. In Proceedings of the twentieth annual ACM symposium on Theory of computing , pages 301--309, 1988

    work page 1988

Show all 37 references
  1. [9]

    Revisiting frequency moment estimation in random order streams

    Vladimir Braverman, Emanuele Viola, David P Woodruff, and Lin F Yang. Revisiting frequency moment estimation in random order streams. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) . Schloss-Dagstuhl-Leibniz Zentrum f \"u r Informatik, 2018

    2018

  2. [10]

    An information statistics approach to data stream and communication complexity

    Ziv Bar-Yossef, Thathachar S Jayram, Ravi Kumar, and D Sivakumar. An information statistics approach to data stream and communication complexity. Journal of Computer and System Sciences , 68(4):702--732, 2004

    2004

  3. [11]

    Optimality of frequency moment estimation

    Mark Braverman and Or Zamir. Optimality of frequency moment estimation. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC) , Prague, Czech Republic, June 2025

    2025

  4. [12]

    Near-optimal lower bounds on the multi-party communication complexity of set disjointness

    Amit Chakrabarti, Subhash Khot, and Xiaodong Sun. Near-optimal lower bounds on the multi-party communication complexity of set disjointness. In 18th IEEE Annual Conference on Computational Complexity, 2003. Proceedings. , pages 107--117. IEEE, 2003

    2003

  5. [13]

    An optimal lower bound on the communication complexity of gap-hamming-distance, 2012

    Amit Chakrabarti and Oded Regev. An optimal lower bound on the communication complexity of gap-hamming-distance, 2012

    2012

  6. [14]

    Sivakumar

    Anirban Dasgupta, Ravi Kumar, and D. Sivakumar. Sparse and lopsided set disjointness via information theory. In Anupam Gupta, Klaus Jansen, Jos \'e Rolim, and Rocco Servedio, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , pag...

    2012

  7. [15]

    An introduction to probability theory and its applications

    William Feller. An introduction to probability theory and its applications. V ol. II . Second edition. John Wiley & Sons Inc., New York, 1971

    1971

  8. [16]

    A lower bound for estimating high moments of a data stream

    Sumit Ganguly. A lower bound for estimating high moments of a data stream. arXiv preprint arXiv:1201.0253 , 2011

    2011 arXiv

  9. [17]

    Polynomial estimators for high frequency moments

    Sumit Ganguly. Polynomial estimators for high frequency moments. arXiv preprint arXiv:1104.4552 , 2011

    2011 arXiv

  10. [18]

    Fast, small-space algorithms for approximate histogram maintenance

    Anna C Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, Sivaramakrishnan Muthukrishnan, and Martin J Strauss. Fast, small-space algorithms for approximate histogram maintenance. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing , pages 389--398, 2002

    2002

  11. [19]

    T. E. Harris. A lower bound for the critical probability in a certain percolation process. Mathematical Proceedings of the Cambridge Philosophical Society , 56(1):13–20, 1960

    1960

  12. [20]

    Optimal approximations of the frequency moments of data streams

    Piotr Indyk and David Woodruff. Optimal approximations of the frequency moments of data streams. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing , pages 202--208, 2005

    2005

  13. [21]

    Towards optimal moment estimation in streaming and distributed models

    Rajesh Jayaram and David P Woodruff. Towards optimal moment estimation in streaming and distributed models. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) . Schloss-Dagstuhl-Leibniz Zentrum f \"u r Informatik, 2019

    2019

  14. [22]

    On the exact space complexity of sketching and streaming small norms

    Daniel M Kane, Jelani Nelson, and David P Woodruff. On the exact space complexity of sketching and streaming small norms. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms , pages 1161--1178. SIAM, 2010

    2010

  15. [23]

    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 conference on Internet measurement , pages 234--247, 2003

    2003

  16. [24]

    Improved sparse multivariate polynomial interpolation algorithms

    Erich Kaltofen and Lakshman Yagati. Improved sparse multivariate polynomial interpolation algorithms. In International Symposium on Symbolic and Algebraic Computation , pages 467--474. Springer, 1988

    1988

  17. [25]

    A tight lower bound for high frequency moment estimation with small error

    Yi Li and David P Woodruff. A tight lower bound for high frequency moment estimation with small error. In International Workshop on Approximation Algorithms for Combinatorial Optimization , pages 623--638. Springer, 2013

    2013

  18. [26]

    Communication complexity of approximating the size of set intersection, June 2018

    Jeřábek Meir. Communication complexity of approximating the size of set intersection, June 2018. Theoretical Computer Science, Stack Exchange

    2018

  19. [27]

    1-pass relative-error lp-sampling with applications

    Morteza Monemizadeh and David P Woodruff. 1-pass relative-error lp-sampling with applications. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms , pages 1143--1160. SIAM, 2010

    2010

  20. [28]

    Private vs

    Ilan Newman. Private vs. common random bits in communication complexity. Information Processing Letters , 39(2):67--71, 1991

    1991

  21. [29]

    Optimal bounds for approximate counting

    Jelani Nelson and Huacheng Yu. Optimal bounds for approximate counting. In Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems , pages 119--127, 2022

    2022

  22. [30]

    Shevtsova

    Irina G. Shevtsova. On the absolute constant in the berry--esseen inequality. Doklady Mathematics , 82(3):862--864, 2010

    2010

  23. [31]

    Schmidt, Alan Siegel, and Aravind Srinivasan

    Jeanette P. Schmidt, Alan Siegel, and Aravind Srinivasan. Chernoff–hoeffding bounds for applications with limited independence. SIAM Journal on Discrete Mathematics , 8(2):223--250, 1995

    1995

  24. [32]

    On the Communication Complexity of Sparse Set Disjointness and Exists-Equal Problems

    Mert Saglam and Gabor Tardos. On the Communication Complexity of Sparse Set Disjointness and Exists-Equal Problems . In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS) , pages 678--687, Los Alamitos, CA, USA, October 2013. IEEE Computer Society

    2013

  25. [33]

    Optimal space lower bounds for all frequency moments

    David P Woodruff. Optimal space lower bounds for all frequency moments. In SODA , volume 4, pages 167--175. Citeseer, 2004

    2004

  26. [34]

    Tight bounds for distributed functional monitoring

    David P Woodruff and Qin Zhang. Tight bounds for distributed functional monitoring. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing , pages 941--960, 2012

    2012

  27. [35]

    Separations for estimating large frequency moments on data streams

    David P Woodruff and Samson Zhou. Separations for estimating large frequency moments on data streams. In ICALP , 2021

    2021

  28. [36]

    Andrew C. Yao. Probabilistic computations: Toward a unified measure of complexity. In Proceedings of the 18th Annual Symposium on Foundations of Computer Science (FOCS) , pages 222--227. IEEE, 1977

    1977

  29. [37]

    Probabilistic algorithms for sparse polynomials

    Richard Zippel. Probabilistic algorithms for sparse polynomials. In International symposium on symbolic and algebraic manipulation , pages 216--226. Springer, 1979

    1979

Pith tools

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