Element distinctness, frequency moments, and sliding windows

We consider time-space tradeoffs for exactly computing frequency
moments and order statistics over sliding windows~\cite{dgim: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
$T\cdot S \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\ne 1$.

We complement this lower bound with a $T\cdot S \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 the 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.

Using this reduction we present a family of randomized algorithms for
sliding-window element distinctness
with a heuristic analysis of $T^2\cdot S\in \tilde O(n^3)$, which
is strictly smaller than our lower bound
for sliding-window $F_0\bmod 2$ for $S$ smaller than $n/\mathrm{polylog} (n)$.

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 $T\cdot S \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.