  We revisit the complexity of online computation in the cell probe model. We
consider a class of problems where we are first given a fixed pattern or vector
$F$ of $n$ symbols and then one symbol arrives at a time in a stream. After
each symbol has arrived we must output some function of $F$ and the $n$-length
suffix of the arriving stream. Cell probe bounds of $\Omega(\delta\lg{n}/w)$
have previously been shown for both convolution and Hamming distance in this
setting, where $\delta$ is the size of a symbol in bits and
$w\in\Omega(\lg{n})$ is the cell size in bits. However, when $\delta$ is a
constant, as it is in many natural situations, these previous results no longer
give us non-trivial bounds.
  We introduce a new lop-sided information transfer proof technique which
enables us to prove meaningful lower bounds even for constant size input
alphabets. We use our new framework to prove an amortised cell probe lower
bound of $\Omega(\lg^2 n/(w\cdot \lg \lg n))$ time per arriving bit for an
online version of a well studied problem known as pattern matching with address
errors. This is the first non-trivial cell probe lower bound for any online
problem on bit streams that still holds when the cell sizes are large. We also
show the same bound for online convolution conditioned on a new combinatorial
conjecture related to Toeplitz matrices.
