Date: 21 Feb 2017
From: jyrki@di.ku.dk
Subject: A one-day visit

Guest lecture: On-the-Fly Array Initialization in Less Space
Speaker: Torben Hagerup, Universität Augsburg
Time: Thursday, 23 February 2017 at 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