Backup diff of iwsk(No. 11) - ALG-Lab. PukiWiki

List of Backups
View the source.
View the backup.
iwsk has been deleted.
- 1 (2008-05-15 (Thu) 00:35:19)
- 2 (2008-05-15 (Thu) 02:12:33)
- 3 (2008-05-15 (Thu) 05:22:39)
- 4 (2008-05-19 (Mon) 01:40:01)
- 5 (2008-05-19 (Mon) 05:31:36)
- 6 (2008-05-19 (Mon) 10:58:45)
- 7 (2008-05-27 (Tue) 00:14:55)
- 8 (2008-05-29 (Thu) 05:39:19)
- 9 (2008-05-29 (Thu) 05:39:19)
- 10 (2008-05-29 (Thu) 05:39:19)
- 11 (2008-05-29 (Thu) 05:39:19)

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]

Backup diff of iwsk (No. 11)