Merkleの基準のSchnorrおよびKurtzランダムネス版

履歴
2013年3月19日 原稿,スライドをアップロード

タイトル
Merkleの基準のSchnorrおよびKurtzランダムネス版

種類
研究集会

発表場所
コンピュテーション(COMP)研究会
岐阜大学 2013年3月18日(月)
電子情報通信学会技術研究報告 信学技報 (IEICE Technical Report) Vol. 112 No. 498
COMP 2012-60, pp55-59

ダウンロード
スライド
プレプリント

Van Lambalgen’s Theorem for uniformly relative Schnorr and computable randomness

履歴
2013年2月受理
2012年9月26日arXivにアップロード
2012年8月投稿

タイトル
Van Lambalgen’s Theorem for uniformly relative Schnorr and computable randomness
(with Jason Rute)

種類
査読ありの事後会議録

国際会議と雑誌
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 from arXiv