What is random?

News
12 Dec 2015, the slide was uploaded

Title
What is random?

Type
Ikura salon at Meiji University

The slide and the talk is in Japanese.

Download
Slide

Posted in Talks | Leave a comment

Separation of randomness notions in Weihrauch degrees

News
2 Oct 2015, the abstract was uploaded

Title
Separation of randomness notions in Weihrauch degrees

Type
Short talk on black boards at Dagstuhl Seminar

Abstract
If someone says that a function is “computable”, it sometimes means that it is programmable with a programming language with a random generator. Computability with a random set can be paid more attension. In this talk we will consider whether we can make a random set more random. In other words, we will consider randomness notions in Weihrauch degrees and see some separation of them.
This is a joint work with Rupert Hölzl.

Posted in Talks | Leave a comment

Characterizations of 3-randomness via complexity

News
8 Sep 2015, the slide file was uploaded

Title
Characterizations of 3-randomness via complexity

Type
Talk at MSJ Autumn Meeting 2015

Download
miyabe-mathsoc2015Sep

Posted in Talks | Leave a comment

Reducibilities as refinements of the randomness hierarchy

News
8 Sep 2015, the slide file was uploaded

Title
Reducibilities as refinements of the randomness hierarchy

Type
Talk at CTFM2015

Download
miyabe-ctfm2015

Posted in Talks | Leave a comment

Welcome to mathematical paradoxes

News
29 July 2015, the slide file was uploaded

Title
Welcome to mathematical paradoxes

Type
Summer Seminar of Meiji University for high school students

Download
summer-seminar

Posted in Talks | Leave a comment

Using Almost-Everywhere Theorems from Analysis to Study Randomness

News
May 2015, Resubmitted.
3 Nov 2014. Submitted

Title
Using Almost-Everywhere Theorems from Analysis to Study Randomness
(with Jing Zhang and Andre Nies)

Type
Full paper

Journal
Submitted
arXiv
The latest version is here.

Abstract
We study algorithmic randomness notions via effective versions of almost-everywhere theorems from analysis and ergodic theory. The effectivization is in terms of objects described by a computably enumerable set, such as lower semicomputable functions. The corresponding randomness notions are slightly stronger than Martin-Lo ̈f (ML) randomness. We establish several equivalences. Given a ML-random real z, the additional randomness strengths needed for the following are equivalent.
(1) all effectively closed classes containing z have density 1 at z.
(2) all nondecreasing functions with uniformly left-c.e. increments are differentiable at z.
(3) z is a Lebesgue point of each lower semicomputable integrable function.
We also consider convergence of left-c.e. martingales, and convergence in the sense of Birkhoff’s pointwise ergodic theorem. Lastly we study randomness notions for density of $\Pi^0_n$ and $\Sigma^1_1$ classes.

Posted in Publication | Leave a comment

Schnorr triviality and its equivalent notions

News
13 Sep 2013, Accepted by TOCS
23 Mar 2013, Submitted

Title
Schnorr triviality and its equivalent notions

Type
Full paper

Journal
Theory of Computing Systems
Volume 56, Issue 3 , pp 465-486
DOI: 10.1007/s00224-013-9506-8

Download
preprint
KURENAI

Posted in Publication | Leave a comment

Unified Characterizations of Lowness Properties via Kolmogorov Complexity

News
19 Jan 2014, submitted
24 Mar 2015, published

Title
Unified Characterizations of Lowness Properties via Kolmogorov Complexity
(with T. Kihara)

Type
Full paper

Journal
Archive for Mathematical Logic: Volume 54, Issue 3 (2015), Page 329-358
DOI: 10.1007/s00153-014-0413-8

Abstract
Consider a randomness notion $\mathcal C$.
A uniform test in the sense of $\mathcal C$ is a total computable procedure that each oracle $X$ produces a test relative to $X$ in the sense of $\mathcal C$.
We say that a binary sequence $Y$ is $\mathcal C$-random uniformly relative to $X$ if $Y$ passes all uniform $\mathcal C$ tests relative to $X$.

Suppose now we have a pair of randomness notions $\mathcal C$ and $\mathcal D$ where $\mathcal{C}\subseteq \mathcal{D}$, for instance Martin-L\”of randomness and Schnorr randomness. Several authors have characterized classes of the form Low($\mathcal C, \mathcal D$) which consist of the oracles $X$ that are so feeble that $\mathcal C \subseteq \mathcal D^X$. Our goal is to do the same when the randomness notion $\mathcal D$ is relativized uniformly: denote by Low$^\star$($\mathcal C, \mathcal D$) the class of oracles $X$ such that every $\mathcal C$-random is uniformly $\mathcal D$-random relative to $X$.

(1) We show that $X\in{\rm Low}^\star({\rm MLR},{\rm SR})$ if and only if $X$ is c.e.~tt-traceable if and only if $X$ is anticomplex if and only if $X$ is Martin-L\”of packing measure zero with respect to all computable dimension functions.

(2) We also show that $X\in{\rm Low}^\star({\rm SR},{\rm WR})$ if and only if $X$ is computably i.o.~tt-traceable if and only if $X$ is not totally complex if and only if $X$ is Schnorr Hausdorff measure zero with respect to all computable dimension functions.

Download
preprint

Posted in Publication | Leave a comment

The randomness hierarchy and reducibilities as its refinements

News
23 Feb 2015, the slide file was uploaded

Title
The randomness hierarchy and reducibilities as its refinements

Type
Joint seminar at TMU (in Japanese)

Download
TMU-slide in Japanese

Posted in Talks | Leave a comment

Total-machine reducibility and randomness notions

News
4 Jan 2015, the slide file was uploaded

Title
Total-machine reducibility and randomness notions

Type
Asian Logic Conference 2015

Download
slide

Posted in Talks | Leave a comment