Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:On-the-fly array initialization
Speaker:Prof. Torben Hagerup
coming from:Universit├Ąt Augsburg
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 20 December 2016
Duration:30 Minutes
Building:E1 4
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+ceiling(n (t/(2 w))^t) 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+ceiling(n/(w^t)) 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.
Name(s):Christina Fries
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
Christina Fries/AG1/MPII/DE, 12/15/2016 09:43 AM
Last modified:
halma/MPII/DE, 11/07/2018 04:52 PM
  • Christina Fries, 12/15/2016 02:17 PM
  • Christina Fries, 12/15/2016 09:46 AM -- Created document.