## Computable Measure Theory

News
11 Mar 2018, Submitted

Title
Computable Measure Theory

Type
Survey in Japanese

Journal
RIMS Kokyuroku 25 – 27 Dec 2017

rims

## Null-additivity in the theory of algorithmic randomness

News
Gave up for publication.
Rejected.

Title
Null-additivity in the theory of algorithmic randomness

Type
Full paper

Journal

Abstract

## Using Almost-Everywhere Theorems from Analysis to Study Randomness

News
10 Oct 2016, published online
29 Feb 2016, Accepted by BSL
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
The Bulletin of Symbolic Logic, Volume 22, Issue 3
September 2016, pp. 305-331
arXiv

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.

## Reducibilities relating to Schnorr randomness

News
22 Sep 2014. Accepted to publish in TOCS
24 Mar 2014. Submitted

Title
Reducibilities relating to Schnorr randomness

Type
Full paper

Journal
Theory of Computing Systems, 58(3), 441-462, 2016.
DOI: 10.1007/s00224-014-9583-3

Abstract
Some measures of randomness have been introduced for Martin- L ̈of randomness such as K-reducibility, C-reducibility and vL-reducibility. In this paper we study Schnorr-randomness versions of these reducibilities. In particular, we characterize the computably-traceable reducibility via relative Schnorr randomness, which was asked in Nies’ book (Problem 8.4.22). We also show that Schnorr reducibility implies uniform-Schnorr-randomness version of vL-reducibility, which is the Schnorr-randomness version of the result that K-reducibility implies vL-reducibility.

preprint

## 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 (2015)
Volume 56, Issue 3 , pp 465-486
DOI: 10.1007/s00224-013-9506-8