Skip to main content
Link
Menu
Expand
(external link)
Document
Search
Copy
Copied
NobuNote
Home
よく使う道具
記法
よく使う不等式
便利な不等式
エクスパンダーグラフ
ランダムグラフ
サンプラー
行列のスペクトル
ペア独立性
統計距離
ランダムネス抽出器
Learning with Error
BKWアルゴリズム
埋め込みクリーク問題
Kučeraのアルゴリズム
AKSアルゴリズム
探索から判定への帰着
平均時計算量理論
問題の平均時困難性
関数の擬似ランダム性
ハードコア補題
Goldreich-Levinの定理
XOR補題
直積定理
誤り訂正符号
復号化
符号の限界
Hadamard符号
Reed-Solomon符号
folded Reed-Solomon符号
連接符号
AEL距離増幅
ランダム線形符号
最悪時から平均時への帰着
行列積
PCP定理
DinurのPCP定理証明
高次元エクスパンダー
メモ
GMW91
IJKW10
VZ25
製作者: 清水 伸高
理論計算機科学, 特に平均時計算量(average-case complexity)に関する様々な手法やアルゴリズム, そしてその基となる道具について出来るだけ分かり易く解説していきます.