タイトル
Schnorr triviality is equivalent to being a basis for tt-Schnorr randomness
種類
口頭発表
発表場所
京都大学数理解析研究所計算機科学セミナー
2012年6月7日
アブストラクト
ランダムの概念として最も有名なMartin-L\”ofランダムネスは，
テスト，複雑性，マルチンゲールなどにより特徴付けられる．
一方，ランダムではない（遠い）という概念として，
low,trivial,basisなどの概念が存在し，
これらが同値になる事が知られている．(Nies 2005, Hirschfeldt et al. 2007)
このSchnorrランダムネス版について，適当な相対化を行えば，
lowとtrivialは同値になる．(Franklin-Stephan 2010)
一方，basisによる(自然な)同値な定義は知られていなかった．
本講演では，basisによる特徴付けなど，
Schnorr trivialityに関するいくつかの新しい結果を紹介する．
補足
前半30分は日本語で，Martin-L\”ofランダムネスに対する，
low,triviality,basisなどの概念を紹介する．
後半30分は英語で，Schnorrランダムネスに関する
講演者の結果を発表する．
後半はCCR2012で発表する予定である．
ダウンロード
前半用スライド
後半用スライドなどはCCR用のページからダウンロードできます