Tight lower bound for linear sketches of moments

Alexandr Andoni, Huy L. Nguyên, Yury Polyanskiy, Yihong Wu

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationAutomata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings
Number of pages8
EditionPART 1
StatePublished - 2013
Externally publishedYes
Event40th International Colloquium on Automata, Languages, and Programming, ICALP 2013 - Riga, Latvia
Duration: Jul 8 2013Jul 12 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume7965 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other40th International Colloquium on Automata, Languages, and Programming, ICALP 2013

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Tight lower bound for linear sketches of moments'. Together they form a unique fingerprint.

Cite this