On the Space Complexity of Online Convolution

Joel Daniel Andersson, Amir Yehudayoff

We study a discrete convolution streaming problem. An input arrives as a stream of numbers $z=(z_0,z_1,z_2,\dots )$, and at time $t$ our goal is to output $(Tz{)}_t$ where $T$ is a…