Optimal redundancy in computations from random oracles
From MaRDI portal
Abstract: 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.
Recommendations
Cites work
- A basis theorem for Π₁⁰ classes of positive measure and jump inversion for random reals
- A Theory of Program Size Formally Identical to Information Theory
- Algorithmic randomness and complexity.
- Calibrating Randomness
- Computability and randomness
- Every sequence is reducible to a random one
- Forbidden information
- scientific article; zbMATH DE number 4008384 (Why is no real title available?)
- scientific article; zbMATH DE number 4093436 (Why is no real title available?)
- scientific article; zbMATH DE number 736618 (Why is no real title available?)
- scientific article; zbMATH DE number 1010621 (Why is no real title available?)
- scientific article; zbMATH DE number 1543075 (Why is no real title available?)
- scientific article; zbMATH DE number 4118353 (Why is no real title available?)
- scientific article; zbMATH DE number 5064956 (Why is no real title available?)
- Jump inversions inside effectively closed sets and applications to randomness
- Logical Approaches to Computational Barriers
- Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers
- Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity
- On Languages Reducible to Algorithmically Random Languages
- On the construction of effectively random sets
- Randomness and Computability: Open Questions
- The definition of random sequences
Cited in
(6)- The Kučera-Gács theorem revisited by Levin
- Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers
- Limits of the Kučera–Gács Coding Method
- Random Oracle Reducibility
- Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle?
- Extending CL-reducibility on array noncomputable degrees
This page was built for publication: Optimal redundancy in computations from random oracles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1678164)
