Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Algorithmic Randomness:
TR10-150 | 19th September 2010
Bjørn Kjos-Hanssen

A strong law of computationally weak subsets

We show that in the setting of fair-coin measure on the power set of the natural numbers, each sufficiently random set has an infinite subset that computes no random set. That is, there is an almost sure event $\mathcal A$ such that if $X\in\mathcal A$ then $X$ has an infinite ... more >>>

TR23-201 | 16th October 2023
Alexander Shekhovtsov, Georgii Zakharov

Enumerating Complexity Revisited

We reduce the best-known upper bound on the length of a program that enumerates a set in terms of the probability of it being enumerated by a random program. We prove a general result that any linear upper bound for finite sets implies the same linear bound for infinite sets.

... more >>>

ISSN 1433-8092 | Imprint