**News**

1 Feb 2016, accepted by TOCS

**Title**

Coherence of reducibilities with randomness notions

**Type**

Full paper

**Journal**

TOCS, post proceedings of CCR2016

**Abstract**

Loosely speaking, when $A$ is “more random” than $B$ and $B$ is “random”,

then $A$ should be random.

The theory of algorithmic randomness has some formulations of “random” sets

and “more random” sets.

In this paper, we study which pairs $(R,r)$ of randomness notions $R$

and reducibilities $r$ have the follwing property:

if $A$ is $r$-reducible to $B$ and $A$ is $R$-random,

then $B$ should be $R$-random.

The answer depends on the notions $R$ and $r$.

The implications hold for most pairs, but not for some.

We also give characterizations of $n$-randomness via complexity.

**download**

preprint