All reports by Author Widad Machmouchi:

__
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

__
TR10-104
| 29th June 2010
__

Paul Beame, Widad Machmouchi#### Making RAMs Oblivious Requires Superlogarithmic Overhead

Revisions: 3
,
Comments: 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 >>>

Paul Beame, Widad Machmouchi

We prove a time-space tradeoff lower bound of $T =

\Omega\left(n\log(\frac{n}{S}) \log \log(\frac{n}{S})\right) $ for

randomized oblivious branching programs to compute $1GAP$, also

known as the pointer jumping problem, a problem for which there is a

simple deterministic time $n$ and space $O(\log n)$ RAM (random

access machine) algorithm.

In ... more >>>