**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

宮部賢志（ミヤベケンシ）

**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

**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

**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

**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

**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

**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

**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

Posted in Publication
Leave a comment

**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

**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

**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