Erratum for: Approximating and Testing k-Histogram Distributions in Sub-linear Time
Summary: Erratum to PODS'12: corrects Theorem 2's time bound from Õ((k/ε)^2 ln n) to Õ((k^5/ε^4) ln^2 n) while leaving sample complexity unchanged (still Õ((k/ε)^2 ln n)). Error traced to iteration count in Step (7); corrected proof posted as ECCC TR11-171 Rev.1. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Piotr Indyk
- 2. Reut Levi
- 3. Ronitt Rubinfeld
Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 1 of 1 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 6,637 | Approximating and Testing k-Histogram Distributions in Sub-linear Time | 2012 | PODS | 4.9816401e-05 |
Previous
Page 1 / 1
Next