  A classic result in algorithmic information theory is that every infinite
binary sequence is computable from a Martin-Loef random infinite binary
sequence. Proved independently by Kucera and Gacs, this result answered a
question by Charles Bennett and has seen numerous applications in the last 30
years. The optimal redundancy in such a coding process has, however, remained
unknown. If the computation of the first n bits of a sequence requires n + g(n)
bits of the random oracle, then g is the redundancy of the computation. Kucera
implicitly achieved redundancy n log n while Gacs used a more elaborate
block-coding procedure which achieved redundancy sqrt(n) log n. Different
approaches to coding such as the one by Merkle and Mihailovic have not improved
this redundancy bound. In this paper we devise a new coding method that
achieves optimal logarithmic redundancy. Our redundancy bound is exponentially
smaller than the previously best known bound and is known to be the best
possible. It follows that redundancy r log n in computation from a random
oracle is possible for every stream, if and only if r > 1.
