Open Collections

Optimal redundancy in computations from random oracles

Banff International Research Station for Mathematical Innovation and Discovery

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 talk 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 also shown 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.

Mathematics; Mathematical logic and foundations; Dynamical systems and ergodic theory; Logic and foundations

video/mp4

Author affiliation: Chinese Academy of Sciences

2017-06-08

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/61885

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/