All reports by Author Raphael Clifford:

__
TR13-127
| 15th September 2013
__

Paul Beame, Raphael Clifford, Widad Machmouchi#### Element Distinctness, Frequency Moments, and Sliding Windows

__
TR12-178
| 18th December 2012
__

Paul Beame, Raphael Clifford, Widad Machmouchi#### Sliding Windows With Limited Storage

Revisions: 1

Paul Beame, Raphael Clifford, Widad Machmouchi

We derive new time-space tradeoff lower bounds and algorithms for exactly computing statistics of input data, including frequency moments, element distinctness, and order statistics, that are simple to calculate for sorted data. In particular, we develop a randomized algorithm for the element distinctness problem whose time $T$ and space $S$ ... more >>>

Paul Beame, Raphael Clifford, Widad Machmouchi

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 ...
more >>>