# Category Archives: Publication

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

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

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.

## 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.

**Download**

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

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

## Mathematical Seminar, Oct 2014

An article was published in Mathematical Seminar Oct 2014.

## Derandomization in Game-Theoretic Probability

**News**

27 Sep 2014, Online

3 Aug 2014, Accepted in SPA

12 Feb 2014. Submitted

**Title**

Derandomization in Game-Theoretic Probability

(with A. Takemura)

**Type**

Full paper

**Journal**

Stochastic Processes and their Applications 125, 39-59, 2015

**Abstract**

We give a general method for constructing a deterministic strategy

of Reality from a randomized strategy in game-theoretic probability.

The construction can be seen as derandomization in game-theoretic probability.

**Download**

preprint

## Algorithmic randomness over general spaces

**News**

7 May 2014. Published online

Dec 2013. Accepted

May, 2012. Resubmit

Sep, 2011. Resubmitted a revised version

25 May, 2010. Submitted to a Journal

**Title**

Algorithmic randomness over general spaces

**Type**

Fullpaper

**Journal**

Math. Log. Quart. 60, No. 3, 184–204 (2014)

DOI 10.1002/malq.201200051

**Download**

preprint

**Abstract**

The study of Martin-Löf randomness on a computable metric space with a computable measure has had much progress recently.

In this paper we study Martin-Löf randomness on a more general space, that is, a computable topological space with a computable measure.

On such a space, Martin-Löf randomness may not be a natural notion because there is not a universal test, and Martin-Löf randomness and complexity randomness (defined in this paper) do not coincide in general. We show that SCT3 is a sufficient condition for the existence and the coincidence and study how much we can weaken the condition.

## $L^1$-computability, layerwise computability and Solovay reducibility

**News**

17 July 2013, published

27 Mar 2013, accepted

19 Sep 2012, submitted

**Title**

L1-computability, layerwise computability and Solovay reducibility

**Type**

Full paper

**Journal**

Computability, 2:15-29, 2013.

**Abstract**

We propose a hierarchy of classes of functions that corresponds to the hierarchy of randomness notions. Each class of functions converges at the corresponding random points. We give various characterizations of the classes, that is, characterizations via integral tests, L1-computability and layerwise computability. Furthermore, the relation among these classes is formulated using Solovay reducibility for lower semicomputable functions.

**Download**

preprint

**Correction**

Proposition 2.3.

Let $\mu$ be a computable measure on a computable metric space.

Then there exists a computable sequence $\{r_n\}$ such that $\mu(\overline{B}(\alpha_i,r_j)\setminus B(\alpha_i, r_j))$ for all $i$ and $j$.

This statement should be the following.

Proposition 2.3.

Let $\mu$ be a computable measure on a computable metric space.

Then there exists a computable sequence $\{r_n\}$ such that

$\{ r_0,r_1, … \}$ is dense in the interval $(0 , \infty)$ and $\mu(\overline{B}(\alpha_i,r_j)\setminus B(\alpha_i, r_j))$ for all $i$ and $j$.

This problem was pointed out by K. Weihrauch on 19 Jan 2014. I appreciate his notice.

## Uniform Kurtz randomness

**News**

4 Nov 2013, Published online

16 May 2013, Submitted to a Journal

**Title**

Uniform Kurtz randomness

(with Takayuki Kihara)

**Type**

Fullpaper

**Journal**

Journal of Logic and Computation, 24 (4): 863-882, 2014

doi: 10.1093/logcom/ext054

**Abstract**

We propose studying uniform Kurtz randomness, which is the uni- form relativization of Kurtz randomness. This notion has more natural properties than the usual relativization. For instance, van Lambalgen’s theorem holds for uniform Kurtz randomness while not for (the usual relativization of) Kurtz randomness. Another advantage is that lowness for uniform Kurtz randomness has many characterizations, such as those via complexity, martingales, Kurtz tt-traceability, and Kurtz dimensional measure.

**Download**

preprint