Speaker: Torben Hagerup, Universität Augsburg
Time: Thursday, 23 February 2017, 13.00 - 14.00
Place: Meeting room SCI-DIKU-HCO-01-0-029

Abstract:

We show that for all given positive integers $n$, $t$ and $w$ with $n < 2^w$, an array of $n$ entries of $w$ bits each can be represented on a word RAM with a word length of $w$ bits in at most $n w + \lceil n (t / (2 w))^t \rceil$ bits of uninitialized memory to support constant-time initialization of the whole array and $O(t)$-time reading and writing of individual array entries. At one end of this tradeoff, we achieve initialization and access (i.e., reading and writing) in constant time with $n w + \lceil n / (w^t) \rceil$ bits for arbitrary fixed $t$, to be compared with $n w + \Theta(n)$ bits for the best previous solution, and at the opposite end, still with constant-time initialization, we support $O(\log n)$-time access with just $n w + 1$ bits, which is optimal for arbitrary access times if the initialization executes fewer than $n$ steps.

Host: http://www.diku.dk/~jyrki/PE-lab/

Slides: http://materials.dagstuhl.de/files/17/17181/17181.TorbenHagerup.Slides.pdf