  We consider time-space tradeoffs for exactly computing frequency moments and
order statistics over sliding windows. Given an input of length 2n-1, the task
is to output the function of each window of length n, giving n outputs in
total. Computations over sliding windows are related to direct sum problems
except that inputs to instances almost completely overlap.
  We show an average case and randomized time-space tradeoff lower bound of TS
in Omega(n^2) for multi-way branching programs, and hence standard RAM and
word-RAM models, to compute the number of distinct elements, F_0, in sliding
windows over alphabet [n]. The same lower bound holds for computing the
low-order bit of F_0 and computing any frequency moment F_k for k not equal to
1. We complement this lower bound with a TS in \tilde O(n^2) deterministic RAM
algorithm for exactly computing F_k in sliding windows.
  We show time-space separations between the complexity of sliding-window
element distinctness and that of sliding-window $F_0\bmod 2$ computation. In
particular for alphabet [n] there is a very simple errorless sliding-window
algorithm for element distinctness that runs in O(n) time on average and uses
O(log{n}) space.
  We show that any algorithm for a single element distinctness instance can be
extended to an algorithm for the sliding-window version of element distinctness
with at most a polylogarithmic increase in the time-space product.
  Finally, we show that the sliding-window computation of order statistics such
as the maximum and minimum can be computed with only a logarithmic increase in
time, but that a TS in Omega(n^2) lower bound holds for sliding-window
computation of order statistics such as the median, a nearly linear increase in
time when space is small.

Computational Complexity;Data Structures and Algorithms