File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Revisiting the direct sum theorem and space lower bounds in random order streams

TitleRevisiting the direct sum theorem and space lower bounds in random order streams
Authors
Issue Date2009
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2009, v. 5555 LNCS PART 1, p. 513-524 How to Cite?
AbstractEstimating frequency moments and L p distances are well studied problems in the adversarial data stream model and tight space bounds are known for these two problems. There has been growing interest in revisiting these problems in the framework of random-order streams. The best space lower bound known for computing the k th frequency moment in random-order streams is Ω(n 1-2.5/k ) by Andoni et al., and it is conjectured that the real lower bound shall be Ω(n 1-2/k ). In this paper, we resolve this conjecture. In our approach, we revisit the direct sum theorem developed by Bar-Yossef et al. in a random-partition private messages model and provide a tight Ω(n 1-2/k /ℓ) space lower bound for any ℓ-pass algorithm that approximates the frequency moment in random-order stream model to a constant factor. Finally, we also introduce the notion of space-entropy tradeoffs in random order streams, as a means of studying intermediate models between adversarial and fully random order streams. We show an almost tight space-entropy tradeoff for L ∞ distance and a non-trivial tradeoff for L p distances. © 2009 Springer Berlin Heidelberg.
Persistent Identifierhttp://hdl.handle.net/10722/188484
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorGuha, Sen_US
dc.contributor.authorHuang, Zen_US
dc.date.accessioned2013-09-03T04:08:39Z-
dc.date.available2013-09-03T04:08:39Z-
dc.date.issued2009en_US
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2009, v. 5555 LNCS PART 1, p. 513-524en_US
dc.identifier.issn0302-9743en_US
dc.identifier.urihttp://hdl.handle.net/10722/188484-
dc.description.abstractEstimating frequency moments and L p distances are well studied problems in the adversarial data stream model and tight space bounds are known for these two problems. There has been growing interest in revisiting these problems in the framework of random-order streams. The best space lower bound known for computing the k th frequency moment in random-order streams is Ω(n 1-2.5/k ) by Andoni et al., and it is conjectured that the real lower bound shall be Ω(n 1-2/k ). In this paper, we resolve this conjecture. In our approach, we revisit the direct sum theorem developed by Bar-Yossef et al. in a random-partition private messages model and provide a tight Ω(n 1-2/k /ℓ) space lower bound for any ℓ-pass algorithm that approximates the frequency moment in random-order stream model to a constant factor. Finally, we also introduce the notion of space-entropy tradeoffs in random order streams, as a means of studying intermediate models between adversarial and fully random order streams. We show an almost tight space-entropy tradeoff for L ∞ distance and a non-trivial tradeoff for L p distances. © 2009 Springer Berlin Heidelberg.en_US
dc.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_US
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_US
dc.titleRevisiting the direct sum theorem and space lower bounds in random order streamsen_US
dc.typeConference_Paperen_US
dc.identifier.emailHuang, Z: hzhiyi@cis.upenn.eduen_US
dc.identifier.authorityHuang, Z=rp01804en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1007/978-3-642-02927-1_43en_US
dc.identifier.scopuseid_2-s2.0-70449090412en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-70449090412&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume5555 LNCSen_US
dc.identifier.issuePART 1en_US
dc.identifier.spage513en_US
dc.identifier.epage524en_US
dc.publisher.placeGermanyen_US
dc.identifier.scopusauthoridGuha, S=7201879124en_US
dc.identifier.scopusauthoridHuang, Z=55494568500en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats