2008-05-21から1日間の記事一覧

WHの定義

Feige-Shamirの論文とGoldreichの教科書で定義が違うことに気付いた. ともに任意のnの多項式程度の長さのz, 任意のPPTM V^*について下記を満たすある無視できる関数 ε が存在することとなっている. Goldreichの方だと, D_nを{0,1}^n上の分布, XをD_nに従う確…