Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2505.00181 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918325967126528 |
|---|---|
| author | Andersson, Joel Daniel Yehudayoff, Amir |
| author_facet | Andersson, Joel Daniel Yehudayoff, Amir |
| contents | We study a discrete convolution streaming problem. An input arrives as a stream of numbers $z = (z_0,z_1,z_2,\ldots)$, and at time $t$ our goal is to output $(Tz)_t$ where $T$ is a lower-triangular Toeplitz matrix. We focus on space complexity; we define a model for studying the memory-size of online continuous algorithms. In this model, algorithms store a buffer of $β(t)$ numbers in order to achieve their goal.
We characterize space complexity using the language of generating functions. The matrix $T$ corresponds to a generating function $G(x)$. When $G(x)$ is rational of degree $d$, it is known that the space complexity is at most $O(d)$. We prove a corresponding lower bound; the space complexity is at least $Ω(d)$. In addition, for irrational $G(x)$, we prove that the space complexity is infinite. We also provide finite-time guarantees. For example, for the generating function $\frac{1}{\sqrt{1-x}}$ that was studied in various previous works in the context of differentially private continual counting, we prove a sharp lower bound on the space complexity; at time $t$, it is at least $Ω(t)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_00181 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Space Complexity of Online Convolution Andersson, Joel Daniel Yehudayoff, Amir Computational Complexity Data Structures and Algorithms We study a discrete convolution streaming problem. An input arrives as a stream of numbers $z = (z_0,z_1,z_2,\ldots)$, and at time $t$ our goal is to output $(Tz)_t$ where $T$ is a lower-triangular Toeplitz matrix. We focus on space complexity; we define a model for studying the memory-size of online continuous algorithms. In this model, algorithms store a buffer of $β(t)$ numbers in order to achieve their goal. We characterize space complexity using the language of generating functions. The matrix $T$ corresponds to a generating function $G(x)$. When $G(x)$ is rational of degree $d$, it is known that the space complexity is at most $O(d)$. We prove a corresponding lower bound; the space complexity is at least $Ω(d)$. In addition, for irrational $G(x)$, we prove that the space complexity is infinite. We also provide finite-time guarantees. For example, for the generating function $\frac{1}{\sqrt{1-x}}$ that was studied in various previous works in the context of differentially private continual counting, we prove a sharp lower bound on the space complexity; at time $t$, it is at least $Ω(t)$. |
| title | On the Space Complexity of Online Convolution |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2505.00181 |