Lecture 8 Applications: Direct Product Theorems

Presentation on theme: "Lecture 8 Applications: Direct Product Theorems"— Presentation transcript:

1 Lecture 8 Applications: Direct Product Theorems
12/23 Additive Combinatorics 輪講 発表者: 玉置 卓

2 概要 Low-degree Polynomial に対する Hardness Amplification (Direct Product) の解析 Low-degree Polynomial: 高々次数dのGF(2)多項式 Hardness Amplification: 最悪時計算量が高い関数から平均計算量が高い関数を構成する効率の良いリダクション Gowers Normを使ったきれいな解析 応用 Low-degree Test と Gowers Norm Mod3 関数の平均計算量解析の改良

3 準備: 平均計算複雑さ さまざまな計算モデル: M の平均計算複雑さ:
P/poly: 多項式サイズ回路 (ゲート: AND, OR, NOT) AC0: P/polyを定数段数に制限 (fanin, fanout: 無限) AC0[2]: AC0 にPARITYゲートも許す Pd: GF(2)上の次数高々dの多項式 の平均計算複雑さ:

4 平均計算複雑さの増幅 なる変換 を見つけたい Direct Sum: Direct Product:
なる変換 を見つけたい 暗号設計, 脱乱択化などに応用 Direct Sum: Direct Product: Direct Sum (Product) Theorem (dream version):

5 Direct Sum Theoremの意味 定義: だから

6 Direct Product Theorem (XOR-lemma) の例
M=P0={定数関数 -1, 1} M=P/poly (Yao’s XOR-Lemma) M=Pd (Viola-Wigderson, 今回のメイン) 平均計算複雑さの定義は変更: Succ -> Corr

7 XOR –Lemma for GF(2)-polynomial
定義: 定理[VW07]:

8 なぜPd を考える? 回路計算量への応用 未解決問題: AC0の下界 [random restriction]:
AC0[2]では? -> [Razborov-Smolensky] 未解決問題: 証明できればlog-depth回路の非線形下界?

9 XOR-lemmaの証明方針 適切なノルムを導入 XOR-lemmaは自明に従う

10 Gowers Norm 定義(Linear combination): 定義(Gowers degree-d Norm)

11 具体例: Linear combination
足し算はBit-wise

12 具体例: Gowers Norm

13 Gowers Norm 定義(Gowers degree-d Norm,複素関数版)
zを得るのに使われた(線形結合で係数が非ゼロの)ベクトル数

14 Main Lemma 補題: 証明の概略: Fact 1. Fact 2. Fact 3.

15 Sub-lemma 補題(Product Property):

16 XOR-lemmaの証明 命題[AKKL03] と組合わせると Main Lemma Sub Lemma

17 残りは・・・ Main Lemma の証明 Low-degree Test (Property Testing)との関連
Modulo関数のCorr. bound の改良

18 Main Lemma, Fact 1

19 Main Lemma, Fact 2

20 Main Lemma, Fact 3 示したいこと 補題 Fact 3の証明

21 Property Testing d次多項式のテスト 成功確率とGowers Normの関係 1. Pick , set
2. Accept iff 成功確率とGowers Normの関係

22 Property Testing テストの成功確率 d次多項式との距離 命題[AKL+03] より, なら 繰り返すと 高い確率で非受理

23 Mod関数のCorr. bound の改良 定義 Corr. Bound (Bourgain) XOR-Lemmaを使うと [VW07]

24 証明 (1/2)

25 証明(2/2)