Category: Publication

News
Feb 2013, accepted
26 Sep 2012, uploaded to arXiv
Aug 2012, submitted

Title
Van Lambalgen’s Theorem for uniformly relative Schnorr and computable randomness
(with Jason Rute)

Type
Full paper

Journal
Proceedings of the Twelfth Asian Logic Conference, World Scientific, 251-270

Abstract
We correct Miyabe’s proof of van Lambalgen’s Theorem for truth-table Schnorr randomness (which we will call uniformly rela- tive Schnorr randomness). An immediate corollary is one direction of van Lambalgen’s theorem for Schnorr randomness. It has been claimed in the literature that this corollary (and the analogous result for com- putable randomness) is a “straightforward modification of the proof of van Lambalgen’s Theorem.” This is not so, and we point out why. We also point out an error in Miyabe’s proof of van Lambalgen’s Theorem for truth-table reducible randomness (which we will call uniformly rel- ative computable randomness). While we do not fix the error, we do prove a weaker version of van Lambalgen’s Theorem where each half is computably random uniformly relative to the other.

Download
Download from arXiv

News
Mar, 2013, Accepted for the presentation in CiE and rejected to the publication in LNCS
15 Jan, 2013, Submitted to a Conference

Title
Lowness for uniform Kurtz randomness

Type
Accepted in informal electronic proceedings in CiE
with T. Kihara

Journal
Submitted

Abstract
We propose studying uniform Kurtz randomness, which is the uniform relativization of Kurtz randomness. One advantage of this notion is that lowness for uniform Kurtz randomness has many character- izations, such as those via complexity, martingales, Kurtz tt-traceability, and Kurtz dimensional measure.

Download
preprint

The results in this paper will be appeared in another paper.

News
Dec 25, 2012, Published
Aug 8, 2012, Published online
July 12, 2012, Accepted with a minor revision
Dec 23, 2011, Need to fix it
Oct 18, 2011, Submitted to a Journal

Title
Characterization of Kurtz randomness by a differentiation theorem

Type
Fullpaper

Journal
Theory of Computing Systems: Volume 52, Issue 1 (2013), Page 113-132
The page in TOCS

Abstract
Brattka, Miller and Nies showed that some major algorithmic randomness notions are characterized via differentiability.
The main goal of this paper is to characterize Kurtz randomness by a differentiation theorem on a computable metric space.
The proof shows that characterization by integral tests plays an essential part and shows that how randomness and differentiation are connected.

Download
preprint