We consider time-space tradeoffs for exactly computing frequencymoments and order statistics over sliding windows.Given an input of length 2n−1, the task is to output the function ofeach window of length n, giving n outputs in total.Computations over sliding windows are related to direct sum problemsexcept that inputs to instances almost completely overlap.

We show an average case and randomized time-space tradeoff lower bound ofTS(n2) for multi-way branching programs, andhence standard RAM and word-RAM models, to compute the numberof distinct elements, F0, in sliding windows over alphabet [n].The same lower bound holds for computing the low-order bit of F0 andcomputing any frequency moment Fk for k=1 .We complement this lower bound with a TSO(n2)deterministic RAM algorithm for exactly computing Fk in sliding windows.

We show time-space separations between the complexity of sliding-window element distinctness and that of sliding-window F0mod2computation.In particular for alphabet [n] there is a very simple errorlesssliding-window algorithm for element distinctness that runs in O(n) time onaverage and uses O(logn) space.

We show that any algorithm for a single element distinctness instancecan be extended to an algorithm for the sliding-window version of elementdistinctness with at most a polylogarithmic increase in the time-space product.

Finally, we show that the sliding-window computation oforder statistics such as the maximum and minimum can be computed with only alogarithmic increase in time, but that a TS(n2) lowerbound holds for sliding-window computation of order statistics such as themedian, a nearly linear increase in time when space is small.\end{itemize}