Lecture 8 Applications: Direct Product Theorems 12/23 Additive Combinatorics 輪講 発表者: 玉置 卓
概要 Low-degree Polynomial に対する Hardness Amplification (Direct Product) の解析 Low-degree Polynomial: 高々次数dのGF(2)多項式 Hardness Amplification: 最悪時計算量が高い関数から平均計算量が高い関数を構成する効率の良いリダクション Gowers Normを使ったきれいな解析 応用 Low-degree Test と Gowers Norm Mod3 関数の平均計算量解析の改良
準備: 平均計算複雑さ さまざまな計算モデル: M の平均計算複雑さ: P/poly: 多項式サイズ回路 (ゲート: AND, OR, NOT) AC0: P/polyを定数段数に制限 (fanin, fanout: 無限) AC0[2]: AC0 にPARITYゲートも許す Pd: GF(2)上の次数高々dの多項式 の平均計算複雑さ:
平均計算複雑さの増幅 なる変換 を見つけたい Direct Sum: Direct Product: なる変換 を見つけたい 暗号設計, 脱乱択化などに応用 Direct Sum: Direct Product: Direct Sum (Product) Theorem (dream version):
Direct Sum Theoremの意味 定義: だから
Direct Product Theorem (XOR-lemma) の例 M=P0={定数関数 -1, 1} M=P/poly (Yao’s XOR-Lemma) M=Pd (Viola-Wigderson, 今回のメイン) 平均計算複雑さの定義は変更: Succ -> Corr
XOR –Lemma for GF(2)-polynomial 定義: 定理[VW07]:
なぜPd を考える? 回路計算量への応用 未解決問題: AC0の下界 [random restriction]: AC0[2]では? -> [Razborov-Smolensky] 未解決問題: 証明できればlog-depth回路の非線形下界?
XOR-lemmaの証明方針 適切なノルムを導入 XOR-lemmaは自明に従う
Gowers Norm 定義(Linear combination): 定義(Gowers degree-d Norm)
具体例: Linear combination 足し算はBit-wise
具体例: Gowers Norm
Gowers Norm 定義(Gowers degree-d Norm,複素関数版) zを得るのに使われた(線形結合で係数が非ゼロの)ベクトル数
Main Lemma 補題: 証明の概略: Fact 1. Fact 2. Fact 3.
Sub-lemma 補題(Product Property):
XOR-lemmaの証明 命題[AKKL03] と組合わせると Main Lemma Sub Lemma
残りは・・・ Main Lemma の証明 Low-degree Test (Property Testing)との関連 Modulo関数のCorr. bound の改良
Main Lemma, Fact 1
Main Lemma, Fact 2
Main Lemma, Fact 3 示したいこと 補題 Fact 3の証明
Property Testing d次多項式のテスト 成功確率とGowers Normの関係 1. Pick , set 2. Accept iff 成功確率とGowers Normの関係
Property Testing テストの成功確率 d次多項式との距離 命題[AKL+03] より, なら 繰り返すと 高い確率で非受理
Mod関数のCorr. bound の改良 定義 Corr. Bound (Bourgain) XOR-Lemmaを使うと [VW07]
証明 (1/2)
証明(2/2)