AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

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.

Christina Fries

--email hidden

passcode not visible

logged in users only