Extractor D3 川原　純

Extractor Extractor : 一様でない確率分布から一様分布に近い分布を作り出す技法。 X x1, x2, ...,xn 例：自然界にある乱数（熱揺らぎ等） 確率分布 サンプリング X x1, x2, ...,xn f (extractor) 正体不明（のことも多い） f(x1), f(x2),..., f(xn) 一様分布に「近い」

Extractor Extractor : 一様でない確率分布から一様分布に近い分布を作り出す技法。 X f(X) 例：自然界にある乱数（熱揺らぎ等） 確率分布 X f (extractor) f(X) 正体不明（のことも多い） 一様分布に「近い」分布

弱い乱数発生源 どんな確率分布からでも一様分布が作り出せる訳ではない 弱い乱数発生源（weak random sources）を考える マルコフ鎖発生源（Markov-chain source） 確率遷移行列 予測不可能発生源（unpredictable source） {0, 1}n上の確率分布 X ビット固定発生源（bit fixing source） {0, 1}n上の確率分布 X で n-k ビットを固定したもの 例： Pr[X=1] = 1 Pr[X=0] = 0 の分布からはどのようにしても作れない 以下の例はすべて {0,1}n 上の確率分布 (k は定数)　に従う 直観的には n ビット中、k ビットがランダム

分布が「近い」とは 定義 T 上の分布 P と Q が ε-close であるとは、 が成り立つこととする。これを分布の統計距離と呼ぶ。 任意の事象 A ⊆ T に対して が成り立つことと同値。

分布がランダムさをもつとは 定義 {0, 1}n 上の確率分布 X の min-エントロピーを以下のように定義する H∞(X) ≧ k なら Ｘ H∞(X) ≧ k なら 任意の x∈{0,1}n に対して 1 log ≧ k Pr[X=x] 直観的には k ビットのランダムさをもつ Pr[X=x] ≦ 2-k

Extractor の（理想的な）目標 　　　　　　　を満たす任意の {0,1}n 上の確率分布 X から1ビットを “extract” する extractor の設計 f: {0,1}n → {0,1} 　　　　　　　　を満たす任意の X に対して、 Pr[x ← X, f(x) = 1] = 1/2 となる f を設計する

理想的なExtractor は構築不可能 を満たす任意の {0,1}n 上の確率分布 X に 定理 　　　　　　　　を満たす任意の {0,1}n 上の確率分布 X に 対して Pr[x ← X, f(x) = 1] = 1/2 となるような f は存在しない 1 証明のアイデア H∞(X) = min f(X) 1 f : {0,1}3 → {0,1} f log pi n = 3 X 1 = 000 1/8 log 1/4 001 1/16 = 2 1/16 1/2 … 1/4 1/16 1/2 1/16 1/4 任意の H∞(Y) ≧ n – 1 を満たす Y について、 f(Y) は一様分布か？ 111 1/8

理想的なExtractor は構築不可能 を満たす任意の {0,1}n 上の確率分布 X に 定理 　　　　　　　　を満たす任意の {0,1}n 上の確率分布 X に 対して Pr[x ← X, f(x) = 1] = 1/2 となるような f は存在しない 1 H∞(Y) = ≧ 2 証明のアイデア log 1/6 f(X) 1 f : {0,1}3 → {0,1} f n = 3 X Y 000 1/8 1/6 f(X) f 001 1/16 1/6 1/16 1/6 … 1/4 1/16 1/6 1/16 1/6 1/4 111 1/8 1/6

理想的なExtractor は不可能 を満たす任意の {0,1}n 上の確率分布 X に 対して、Pr[x ← X, f(x) = 1] = 1/2 となる f は存在しない 証明 ある X に対して、S = {x | f(x) = b} とする。 b は 0 or 1 |S| ≧ 2n-1 となる b が存在する 確率分布 Y を、 f(y) = b となる y には 1/|S| を、 f(y) = b となる y には 0 を割り当てる。 H∞(Y) ≧ n – 1 を満たし、明らかに Pr[y ←Y, f(y) = 1] = 0 or 1 なので、矛盾

Extractor の定義 定義 (k, ε)-extractor とは関数 で、 を満たす任意の {0,1}n 上の確率分布 X に ついて Ext(X, Ud) が一様分布 Um と ε-close になるもの である。 d はシードと考える d を下げる、mを上げるのが目標

BPP アルゴリズムのシミュレート Extractor があれば BPP アルゴリズムをシミュレートできる。 f(w) を計算するBPPアルゴリズムを考える。 となる多項式チューリング機械 A(w, z) が存在する（z ∈ {0,1}m）。 得体のしれない確率分布 X と extractor Ext が存在するなら すべての y ∈ {0,1}d について、Ext(x, y) = z を計算して、 A(w, z) を走らせて、得られた答えの多数決をとる。

Disperser の定義 定義 (k, ε)-disperser とは関数 で、 を満たす任意の {0,1}n 上の確率分布 X に ついて Dis(X, Ud) の台のサイズが少なくとも (1 - ε)2m である Disperser は RP アルゴリズムをシミュレートできる

X ∈ Lk の場合（Lk は次元が k 以上の 上の アフィン部分空間の集合） 　　　　　　　アフィン部分空間の集合） sum-product theorem を使う前 k ≧ 2 log n のとき、extractor の存在を証明（probabilistic method） k ≧ n / 2 のとき、extractor を構築 sum-product theorem を使った後 k ≧ δn, m = 1 のとき、disperser を構築 [Barakら 05] k ≧ δn のとき、optimal extractor を構築 [Bouら 07] 小さな次元で大きな有限体のとき、extractor を構築 [GR05]

X ∈ の場合 sum-product theorem を使う前 k ≧ 2 log n のとき、optimal extractor を構築（ラムゼーグラフ） k ≧ n / 2 のとき、optimal extractor を構築 [CG88] [Vaz 87] sum-product theorem を使った後 k ≧ 0.4999n のとき、optimal extractor を構築 [Bou 07] k ≧ δn, m = 1 のとき、disperser を構築 [BW05]

A statistical version of the Sum-Product Theorem で、　　　　　　 を満たす任意の {0,1}n 上の確率分布 X に ついて Dis(X, Ud) の台のサイズが少なくとも (1 - ε)2m である Sum-Product Theorem は集合のサイズに関する命題なので、 disperser の構築に有用 しかし、extractor は f(X) が一様であることも要求するので、 単に集合の個数を議論するだけでは不十分 H0(A) = |support(A)| Hshannon(A) = ∑-pi log pi H2(A) =

Theorem 3.2.15 (Sum-Product Theorem) F =Fp とする。H0(A) ≦ 0.9 log p を満たすすべての A ⊂ F に対して、H0(A + A) ≧ H0(A)1+ε と H0(A × A) ≧ H0(A)1+ε の少なくとも一方を満たす ε ≧ 0 が存在する。 H0(A) = |support(A)| H2(A) = H0 を H2 や H∞に置き換えた定理が成り立ってほしいが、 実際は成り立たない

F =Fp とする。H0(A) ≦ 0.9 log p を満たすすべての A ⊂ F に対して、 Theorem 3.2.16 F =Fp とする。H0(A) ≦ 0.9 log p を満たすすべての A ⊂ F に対して、 　H0(A × A + A) > (1+ε)H0(A) を満たす ε ≧ 0 が存在する。 H0(A) = |support(A)| H2(A) = H0 を H2 に置き換えた定理が成り立つ H2(A × A + A) > (1+ε)H2(A)

r = min(r(A), r(B), r(C)) とする。 [BW04] は以下の定理を示した。 H2(A) = A, B, C を FP 上の独立な分布とする。 r(X) = H2(X) / log p , r = min(r(A), r(B), r(C)) とする。 [BW04] は以下の定理を示した。 r ≦ 0.9 なら r(A,B,C) ≧ (1+ε)r r >0.9 なら r(A,B,C) = 1 となる定数 ε >0 が存在する。

以下のように関数列 f i を構築する H2(A × A + A) > (1+ε)H2(A) 3t 個の発生源から、少なくとも (1+ε)t H2(A) の エントロピーをもった1つの発生源に変換することができる。 この手法で k ≧δn, c = poly(1/δ) 上の（optimal）extractor を構築した [BW04]