On the Space Complexity of Online Convolution

We study a discrete convolution streaming problem. An input arrives as a stream of numbers z = (z0,z1,z2,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 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 frac1√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).