Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Greg McLellan:

TR22-134 | 23rd September 2022
Greg McLellan, Alexey Milovanov

Some Games on Turing Machines and Power from Random Strings

Revisions: 1

Denote by $R$ the set of strings with high Kolmogorov complexity. In [E. Allender, H. Buhrman, M. Kouck\'y, D. van Melkebeek, and D. Ronneburger.
Power from random strings.
\emph{SIAM Journal on Computing}, 35:1467--1493, 2006.] the idea of using $R$ as an oracle for resource-bounded computation models was presented. This idea ... more >>>

ISSN 1433-8092 | Imprint