Monthly Archives: February 2017

Randomness of randomness deficiency

News
26 Feb, 2016. The slide file was uploaded

Title
Randomness of randomness deficiency

Type
A talk in a seminar with Suzuki lab

Download
slide

Posted in Talks | Leave a comment

Randomness notions in Muchnik and Medvedev degrees

News
26 Feb, 2016. The slide file was uploaded

Title
Randomness notions in Muchnik and Medvedev degrees

Type
A talk in Dagstuhl seminar on “Computability Theory”

Download
slide

Posted in Talks | Leave a comment

Coherence of reducibilities with randomness notions

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

Posted in Publication | Leave a comment