Abstract
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 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 nlength 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, the existing approaches no longer give us nontrivial bounds.
We introduce a lopsided information transfer proof technique which enables us to prove meaningful lower bounds even for constant size input alphabets. Our new framework is capable of proving amortised cell probe lower bounds of Omega(lg^2 n/(w lg lg n)) time per arriving bit. We demonstrate this technique by showing a new lower bound for a problem known as pattern matching with address errors or the L_2rearrangement distance problem. This gives the first nontrivial cell probe lower bound for any online problem on bit streams that still holds when the cell size is large.
BibTeX  Entry
@InProceedings{clifford_et_al:LIPIcs:2016:6382,
author = {Rapha{\"e}l Clifford and Markus Jalsenius and Benjamin Sach},
title = {{CellProbe Lower Bounds for Bit Stream Computation}},
booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)},
pages = {31:131:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770156},
ISSN = {18688969},
year = {2016},
volume = {57},
editor = {Piotr Sankowski and Christos Zaroliagis},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6382},
URN = {urn:nbn:de:0030drops63827},
doi = {10.4230/LIPIcs.ESA.2016.31},
annote = {Keywords: Cellprobe lower bounds, algorithms, data streaming}
}
Keywords: 

Cellprobe lower bounds, algorithms, data streaming 
Seminar: 

24th Annual European Symposium on Algorithms (ESA 2016) 
Issue Date: 

2016 
Date of publication: 

18.08.2016 