TY - GEN

T1 - Tight lower bound for linear sketches of moments

AU - Andoni, Alexandr

AU - Nguyên, Huy L.

AU - Polyanskiy, Yury

AU - Wu, Yihong

PY - 2013

Y1 - 2013

N2 - The problem of estimating frequency moments of a data stream has attracted a lot of attention since the onset of streaming algorithms [AMS99]. While the space complexity for approximately computing the pth moment, for p ∈ (0,2] has been settled [KNW10], for p > 2 the exact complexity remains open. For p > 2 the current best algorithm uses O(n1-2/p log n) words of space [AKO11,BO10], whereas the lower bound is of Ω(n 1-2/p) [BJKS04]. In this paper, we show a tight lower bound of Ω(n1-2/p log n) words for the class of algorithms based on linear sketches, which store only a sketch Ax of input vector x and some (possibly randomized) matrix A. We note that all known algorithms for this problem are linear sketches.

AB - The problem of estimating frequency moments of a data stream has attracted a lot of attention since the onset of streaming algorithms [AMS99]. While the space complexity for approximately computing the pth moment, for p ∈ (0,2] has been settled [KNW10], for p > 2 the exact complexity remains open. For p > 2 the current best algorithm uses O(n1-2/p log n) words of space [AKO11,BO10], whereas the lower bound is of Ω(n 1-2/p) [BJKS04]. In this paper, we show a tight lower bound of Ω(n1-2/p log n) words for the class of algorithms based on linear sketches, which store only a sketch Ax of input vector x and some (possibly randomized) matrix A. We note that all known algorithms for this problem are linear sketches.

UR - http://www.scopus.com/inward/record.url?scp=84880267390&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84880267390&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-39206-1_3

DO - 10.1007/978-3-642-39206-1_3

M3 - Conference contribution

AN - SCOPUS:84880267390

SN - 9783642392054

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 25

EP - 32

BT - Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings

T2 - 40th International Colloquium on Automata, Languages, and Programming, ICALP 2013

Y2 - 8 July 2013 through 12 July 2013

ER -