Limit on the computational power of $\mathrm{C}$-random strings
It resolves a long-standing open problem about the computational power of Kolmogorov complexity-based oracles for complexity theorists.
The paper constructs a universal decompressor for plain Kolmogorov complexity such that the set of random strings does not allow polynomial-time Turing machines to decide the Halting Problem, resolving a problem posed by Eric Allender.
We construct a universal decompressor $U$ for plain Kolmogorov complexity $\mathrm{C}_U$ such that the Halting Problem cannot be decided by any polynomial-time oracle machine with access to the set of random strings $R_{\mathrm{C}_U} = \{x : \mathrm{C}_U(x) \ge |x|\}$. This result resolves a problem posed by Eric Allender regarding the computational power of Kolmogorov complexity-based oracles.