The rate of convergence of computable predictions

News
16 Sep, 2020 The slide file was uploaded.

Title
The rate of convergence of computable predictions

Type
The 2020 annual meeting of the Deutsche Mathematiker-Vereinigung (German Mathematical Society)
Minisymposia: The impact of randomness on computation

DMV

Reverse randomness

News
4 Nov, 2019 The slide file was uploaded.

Title
Reverse randomness

Type
Colloquium talk at Kyoto University on 8 Nov, 2019.

kyoto

Uniform relativization

News
19 June 2019, Online

Title
Uniform relativization

Type
Conference survey paper

Publication
In: Manea F., Martin B., Paulusma D., Primiero G. (eds) Computing with Foresight and Industry. CiE 2019. Lecture Notes in Computer Science, vol 11558. Springer, Cham

Abstract
This paper is a tutorial on uniform relativization. The usual relativization considers computation using an oracle, and the computation may not work for other oracles, which is similar to Turing reduction. The uniform relativization also considers computation using oracles, however, the computation should work for all oracles, which is similar to truth-table reduction. The distinction between these relativizations is important when we relativize randomness notions in algorithmic randomness, especially Schnorr randomness. For Martin-Löf randomness, its usual relativization and uniform relativization are the same so we do not need to care about this uniform relativization.

We focus on two specific examples of uniform relativization: van Lambalgen’s theorem and lowness. Van Lambalgen’s theorem holds for Schnorr randomness with the uniform relativization, but not with the usual relativization. Schnorr triviality is equivalent to lowness for Schnorr randomness with the uniform relativization, but not with the usual relativization. We also discuss some related known results.

preprint
slide

Schnorr triviality via decidable machines

News
29 Mar, 2019 The slide file was uploaded.

Title
Schnorr triviality via decidable machines

Type
Invited talk in CTFM2019
The 9th International Conference on Computability Theory and Foundations of Mathematics
March 21-27, 2019. Wuhan University of Technology, Wuhan, China.
25 Mar, 2019.

slide

Muchnik degrees and Medvedev degrees of the randomness notions

News
18 Mar, 2019 The slide file was uploaded.

Title
Muchnik degrees and Medvedev degrees of the randomness notions

Type
A talk in AMS
Spring Central and Western Joint Sectional Meeting @ University of Hawaii
Friday March 22, 2019, 3:00 p.m.-4:20 p.m.
Special Session on Computability, Complexity, and Learning, I