Name
Abstract | ||
|---|---|---|
We study the relation between streaming algorithms and linear sketching algorithms, in the context of binary updates. We show that for inputs in n dimensions, the existence of efficient streaming algorithms which can process Omega(n(2)) updates implies efficient linear sketching algorithms with comparable cost. This improves upon the previous work of Li, Nguyen and Woodruff [23] and Ai, Hu, Li and Woodruff [3] which required a triple-exponential number of updates to achieve a similar result for updates over integers. We extend our results to updates modulo p for integers p >= 2, and to approximation instead of exact computation. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.4230/LIPIcs.CCC.2019.13 | Leibniz International Proceedings in Informatics |
Keywords | DocType | Volume |
communication complexity,linear sketching,streaming algorithm | Journal | 137 |
ISSN | Citations | PageRank |
1868-8969 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| kaave hosseini | 1 | 0 | 1.35 |
| Shachar Lovett | 2 | 520 | 55.02 |
| Grigory Yaroslavtsev | 3 | 209 | 17.36 |