AC09_yyoshida

吉田悠一

線形性 v.s. e-farの検査
◦ BLR検査
◦ グラフ検査

線形性 v.s. Low Gowers Uniformityの検査
◦ ハイパーグラフ検査

Dictator v.s. No Influential Variableの検査
◦ PCPの検証者の戦略として用いることが出来る。
◦ 近似困難性の証明につながる。

今回は細かい計算は省略する。



関数f:{0,1}n→{-1,1}が線形: x,y, f(x)f(y)=f(x+y)
a1,…,an {0,1}, f(x)=(-1)a1x2+…+anxn
関数fにアクセスするオラクルが与えられた時に、以下
の二つを区別したい
◦ fが線形
◦ fが線形性から遠い: 任意の線形関数gに対してfとgは高々
1/2+e入力でしか一致しない。


完全性: 線形関数を受理する確率
健全性: 線形関数から遠い関数を受理する確率

最終的に行いたいのはCSPの近似困難性の証明。
◦ クエリ回数と健全性のトレードオフを出来るだけ良くすれば、
それだけタイトな近似困難性につながる。
◦ 目標: 1bitクエリを増やせば健全性が半分になる

検査器の性能の向上は本来近似困難性を示すため
の手段であったはずが、目的化している印象。

近似困難性を示すにはPCPと話を結びつける必要が
あるが、差し当たり線形性の検査で練習(?)する。




x,y R{0,1}nを選ぶ。
f(x)f(y)=f(x+y)ならば受理、そうでなければ拒否する。
BLRアルゴリズムは線形性から遠い関数を確率約1/2
で拒否する。
q回のクエリで健全性は1/2q/3となる。


BLRアルゴリズムが1/2+eの確率で関数fを受理する
{iS } xi
ならば、ある集合S[n]が存在して、
は
 S  (1)
と1/2+e入力で一致する。
証明:
1 1
1 1
3
ˆ
Pr[ f ( x) f ( y)  f ( x  y)]    f S   max fˆS
x, y
2 2 S
2 2 S
S*をfˆS が最大になるSとすると、
1 1
1 1 ˆ
Pr[ f ( x)   S * ( x)]   E[ f ( x)  S * ( x)]   f S *
x, y
2 2 x
2 2
 Pr[ f ( x) f ( y )  f ( x  y )]
x, y



x1,…,xk R{0,1}nを選ぶ。
全てのペア(i,j), 1 i<j kに対して、f(xi)f(xj)=f(xi+xj)が
成り立てば受理、そうでなければ拒否する。
q=k+kC2個のクエリに対して、kC2回の検査を行う。関
数が線形性から遠ければ、これらの検査は殆ど独立
であるように振る舞い、健全性は 1
になることが
知られている。
2
q 2 q






x1,…,xd R{0,1}nを選ぶ。
全てのS [d], |S| 2に対して、 i Sf(xi)=f( i Sxi)が成り
立てば受理、そうでなければ拒否する。
q=2d-1回のクエリに対して、2d-d-1回の検査を行う。
もし検査が全て独立とみなせれば、このテストの健全
性は約(q+1)/2qになるが、実際にはそうではない。
完全性cに対して健全性は少なくとも (1  c)  1
2 q  (
c)
d-1次線形性検査に緩和すると、dハイパーグラフ検査
が使える。

関数fS: {0,1}n Rの族{fS}S [d]に対するd次元Gowers
内積を以下のように定める。
fS  U

d



 Ex , x1 ,..., xd   f S  x   xi 
iS

S [ d ] 
関数f: {0,1}n Rのd次元Gowers uniformityを以下
のように定める。
Ud( f ) 

f  U
d
(d-1)次元線形性検査: fが線形かUd(f) eかを区別す
る。

dハイパーグラフ検査は線形関数を確率1で受理する。
関数fがUd(f) e^(2d+1)を満たす時、fがdハイパーグラ
フ検査で受理される確率は高々1/2^(2d-d-1)+e
証明：
只管計算。以下の補題を利用

 f  
2d
S
Ud

d
U
 ( fS )
S[ d ]
U d 1 ( f )  U d ( f )


BLR検査の受理確率をフーリエ係数で表現できたよう
に、ハイパーグラフ検査の受理確率もGowers 内積
/Uniformityで表現することが出来る。
確率1/2^(2d-d-1)+eで受理する関数fに対して以下が
成立。
 2  U d ( f )1/ 2
d

よってGowers Uniformityが小さい関数の受理確率
は低い。

関数f:{0,1}n→{-1,1}がDictator:
i [n], f(x)=(-1)xi
◦ PCP界隈ではLong Codeとして登場する。

以下の二つを区別する検査器を作りたい(これらが区
別出来れば元のNP困難な問題が解ける)。
◦ Dictator
◦ 任意のi [n]に対してxiのinfluenceがある定数以下


その検査器自体がなすCSPの近似困難性が示せる。
d次元ハイパーグラフ検査が使える。
◦ Influenceが大きい関数はGowers Uniformityが大きい。


Additive Combinatoricsの(本資料作成時点での)
応用を概観した。
初等数学: Sum Product Theorem
◦ 組み合わせ論、Extractor

グラフ理論: Regularity Lemma
◦ 性質検査

解析: Gowers Uniforimity
◦ Pseudorandomness, Direct Product Theorem, PCP

近年の応用

(Weak/Strong) Structure Theorem
◦ グラフ、集合、置換etc.に対するRegularity Lemma

Dense Subsets of Pseudorandom Sets
◦ 疎グラフに対するRegularity Lemma

Ergodic Theory
◦ Hard Core Lemma, Average Case Complexity

Download Report