- The added line is THIS COLOR.
- The deleted line is THIS COLOR.
#nofollow
#norelated
* 岩崎のメモ Index[#ne978c35]
#contents
* Circuit Lower Bounds for Merlin-Arthur Classes - Rahul Santhanam(2007)[#c26795e9]
[[Complexity Zoo:http://qwiki.stanford.edu/wiki/Complexity_Zoo]]: 計算クラスの定義まとめ
Domain: 連結開集合(切れ目がなく,縁を含まない)
Integral domain: 整域(ab = 0 のとき a = 0 か b = 0 に決まっているような集合)
* Trading Group Theory for Randomness - Laszlo Babai(1985) [#c0ef2f12]
** Abstract [#gb94ff09]
[[nilpotent group:http://ja.wikipedia.org/wiki/%E7%BE%A4%E8%AB%96]]: べき零群
[[matrix group:http://ja.wikipedia.org/wiki/%E6%AD%A3%E5%89%87%E8%A1%8C%E5%88%97]]: 行列群(線形代数群)
[[finite simple group:http://d.hatena.ne.jp/keyword/%CD%AD%B8%C2%C3%B1%BD%E3%B7%B2]]: 有限単純群
[[random oracle:http://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%83%A0%E3%82%AA%E3%83%A9%E3%82%AF%E3%83%AB]]: ランダムオラクル(全ての入力を値域内のランダムな出力にマッピングする関数)
[[discrete logarithm problem:http://ja.wikipedia.org/wiki/%E9%9B%A2%E6%95%A3%E5%AF%BE%E6%95%B0%E5%95%8F%E9%A1%8C]]: 離散対数問題
black box group: ブラック・ボックス群?
Papadimitriou's games against nature: ?
finite level: ?
''Merlin is the nondeterministic player and Arthur is the random player.''
Solovay-Strassen: Solovay-Strassenテスト(素数判定法)
user vs. expert games - Goldwasser, Micali and Rackoff
** 1. Introduction [#jfc1d66c]
*** 1.1. Randomness vs. mathematical intractability: a tradeoff [#c02c0dc6]
expanding graph:
*** 1.2. Matrix groups [#s072d6d0]
[[Representation Theory:http://www.ams.org/ert/]]
harmonic analysis: ?
[[permutation group:http://ja.wikipedia.org/wiki/%E5%AF%BE%E7%A7%B0%E7%BE%A4]]: 置換群 = 対象群(symmetric group)
integral matrix: 行列積分?
[[number theoretic:http://ja.wikipedia.org/wiki/%E6%95%B0%E8%AB%96]]: 数論
[[Monte Carlo method:http://ja.wikipedia.org/wiki/%E3%83%A2%E3%83%B3%E3%83%86%E3%82%AB%E3%83%AB%E3%83%AD%E6%B3%95]]: モンテカルロ法
[[PP:http://ja.wikipedia.org/wiki/PP_(%E8%A8%88%E7%AE%97%E8%A4%87%E9%9B%91%E6%80%A7%E7%90%86%E8%AB%96)]]: Probabilistic Polynomial time
[[BPP:http://ja.wikipedia.org/wiki/BPP_(%E8%A8%88%E7%AE%97%E8%A4%87%E9%9B%91%E6%80%A7%E7%90%86%E8%AB%96)]]: Bounded-error Probabilistic Polynomial time
* Theory of Computation - Thomas Zeugmann(2007) [#x642e472]
** Part 1: Formal Languages [#y98e3622]