Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with sliding windows:
TR12-178 | 18th December 2012
Paul Beame, Raphael Clifford, Widad Machmouchi

Sliding Windows With Limited Storage

Revisions: 1

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

TR13-127 | 15th September 2013
Paul Beame, Raphael Clifford, Widad Machmouchi

Element Distinctness, Frequency Moments, and Sliding Windows

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

ISSN 1433-8092 | Imprint