File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/978-3-642-02927-1_43
- Scopus: eid_2-s2.0-70449090412
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Revisiting the direct sum theorem and space lower bounds in random order streams
Title | Revisiting the direct sum theorem and space lower bounds in random order streams |
---|---|
Authors | |
Issue Date | 2009 |
Publisher | Springer 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? |
Abstract | Estimating 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 Identifier | http://hdl.handle.net/10722/188484 |
ISSN | 2023 SCImago Journal Rankings: 0.606 |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Guha, S | en_US |
dc.contributor.author | Huang, Z | en_US |
dc.date.accessioned | 2013-09-03T04:08:39Z | - |
dc.date.available | 2013-09-03T04:08:39Z | - |
dc.date.issued | 2009 | en_US |
dc.identifier.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 | en_US |
dc.identifier.issn | 0302-9743 | en_US |
dc.identifier.uri | http://hdl.handle.net/10722/188484 | - |
dc.description.abstract | Estimating 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.language | eng | en_US |
dc.publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ | en_US |
dc.relation.ispartof | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | en_US |
dc.title | Revisiting the direct sum theorem and space lower bounds in random order streams | en_US |
dc.type | Conference_Paper | en_US |
dc.identifier.email | Huang, Z: hzhiyi@cis.upenn.edu | en_US |
dc.identifier.authority | Huang, Z=rp01804 | en_US |
dc.description.nature | link_to_subscribed_fulltext | en_US |
dc.identifier.doi | 10.1007/978-3-642-02927-1_43 | en_US |
dc.identifier.scopus | eid_2-s2.0-70449090412 | en_US |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-70449090412&selection=ref&src=s&origin=recordpage | en_US |
dc.identifier.volume | 5555 LNCS | en_US |
dc.identifier.issue | PART 1 | en_US |
dc.identifier.spage | 513 | en_US |
dc.identifier.epage | 524 | en_US |
dc.publisher.place | Germany | en_US |
dc.identifier.scopusauthorid | Guha, S=7201879124 | en_US |
dc.identifier.scopusauthorid | Huang, Z=55494568500 | en_US |
dc.identifier.issnl | 0302-9743 | - |