宮部賢志（ミヤベケンシ）
タイトル
ゲーム論的確率論入門
種類
口頭発表
発表場所
第29回記号論理と情報科学研究集会 (SLACS 2012)
2011年9月15日（土） ～ 9月16日（日）
京都産業大学むすびわざ館
アブストラクト
ゲーム論的確率論では測度を使わずに確率の理論を展開する．
その手法はランダムネスの理論に強く影響を受けており，
証明では多くの場面でアルゴリズムを作ることが要求される．
そこで何らかの形でコンピュータ科学にも参考になることを
期待して，ゲーム論的確率論の基本的な考え方を解説する．
ダウンロード
スライド
タイトル
Schnorr triviality is equivalent to being a basis for tt-Schnorr randomness
種類
口頭発表
発表場所
Seventh International Conference on Computability, Complexity and Randomness (CCR 2012)
2-6 July 2012, Cambridge, Great Britain
Isaac Newton Institute
アブストラクト
ランダムの概念として最も有名なMartin-L\”ofランダムネスは，
テスト，複雑性，マルチンゲールなどにより特徴付けられる．
一方，ランダムではない（遠い）という概念として，
low,trivial,basisなどの概念が存在し，
これらが同値になる事が知られている．(Nies 2005, Hirschfeldt et al. 2007)
このSchnorrランダムネス版について，適当な相対化を行えば，
lowとtrivialは同値になる．(Franklin-Stephan 2010)
一方，basisによる(自然な)同値な定義は知られていなかった．
本講演では，basisによる特徴付けなど，
Schnorr trivialityに関するいくつかの新しい結果を紹介する．