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