Monthly Archives: March 2016
22 Sep 2014. Accepted to publish in TOCS
24 Mar 2014. Submitted
Reducibilities relating to Schnorr randomness
Theory of Computing Systems, 58(3), 441-462, 2016.
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.
7 Mar 2016, the slide was uploaded
Mass problems for randomness notions
The mathematical Society of Japan in University of Tsukuba
6 Mar 2016, the slide was uploaded
On the notions of randomness and probability
A talk in The Third Meeting of Quantum Foundation Club
The slide and the talk is in Japanese.