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

Skip to content
# Category: Publication

## Schnorr triviality and its equivalent notions

## Unified Characterizations of Lowness Properties via Kolmogorov Complexity

## Mathematical Seminar, Oct 2014

## Derandomization in Game-Theoretic Probability

## Algorithmic randomness over general spaces

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

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

An article was published in Mathematical Seminar Oct 2014.

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

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