标题： 在线卷积的空间复杂度 显示英文标题

标题： On the Space Complexity of Online Convolution

摘要： 我们研究了一个离散卷积流问题。 输入以数字序列 $z = (z_0,z_1,z_2,\ldots)$ 的形式到达，而在时间 $t$ 我们的目标是输出 $(Tz)_t$，其中 $T$ 是一个下三角Toeplitz矩阵。 我们重点关注空间复杂度；该算法可以存储一个长度为 $\beta(t)$ 的缓冲区以实现这一目标。 当算法执行连续操作时，我们刻画了空间复杂度。 矩阵 $T$ 对应于生成函数 $G(x)$。 如果 $G(x)$ 是 $d$ 次有理数，则已知空间复杂度至多为 $O(d)$。 我们证明了相应的下界；空间复杂度至少为 $\Omega(d)$。 此外，对于无理数 $G(x)$，我们证明了空间复杂度是无穷的。 我们还给出了有限时间保证。 例如，在不同差分隐私连续计数的先前各种工作中研究过的生成函数 $\frac{1}{\sqrt{1-x}}$，我们证明了空间复杂度的一个 sharp 下界；在时间 $t$时，它至少为 $\Omega(t)$。 显示英文摘要

摘要： 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; the algorithm can store a buffer of $\beta(t)$ numbers in order to achieve this goal. We characterize space complexity when algorithms perform continuous operations. The matrix $T$ corresponds to a generating function $G(x)$. If $G(x)$ is rational of degree $d$, then it is known that the space complexity is at most $O(d)$. We prove a corresponding lower bound; the space complexity is at least $\Omega(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 $\Omega(t)$.