# On the Space Complexity of Online Convolution

arXiv: https://arxiv.org/abs/2505.00181 · HTML: https://mlsanity.com/paper/2505.00181/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Apr 2025.

## Built on by (most cited first, 2 of 2)

- [Back to Square Roots: An Optimal Bound on the Matrix Factorization Error for Multi-Epoch Differentially Private SGD](https://mlsanity.com/paper/2505.12128/) (2025)
- [Private Continual Counting of Unbounded Streams](https://mlsanity.com/paper/2506.15018/) (2025)

## Abstract (arXiv)

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).