Output details

Lower bounds for processing data with few random accesses to external memory

<10>This article - invited to JACM, and an extension of the PODS'06 paper "Randomized Computations on Large Data Sets: Tight Lower Bounds" - shows how to obtain lower bounds on the number of passes and the storage size of multi-pass data stream algorithms. Together with our paper "Reversal Complexity Revisited" (TCS 2008), it paved the way for results on data stream algorithms, dealing with statistics (Huynh and Ngoc, FOCS 08 and TOCT 12), compression (Gagie and Gawrychowski, ICALP'10), and limited randomness (David and Papakonstantinou, CCC'10). The results of the journal version are much stronger than those presented at PODS (which were not returned for RAE-2008). In particular, the bounds are now arbitrary close to a given function f(n), instead of just up to some fixed polynomial.