Saturday, June 09, 2007

Distinguishing two graphs by a probabilistic oracle machine

我最近在研讀 Goldreich 與 Trevisan 所合著的這篇 paper:

Three theorems regarding testing graph properties
[Goldreich and Trevisan; RSA 2003]

裡面提到一個很重要的東西,叫做 ε-biased sample space (*)。這個跟一般的 uniform sample space 不一樣的地方在於,每個 element 被取到的機率不是均等的,會有一點誤差,而誤差範圍在 ε 以內。

M 表示一個只能做 o(N^2) 次 queries 的 probabilistic oracle machine。M 擁有的 oracle 即為 input graph,令其為 G,我們假設 query G 中任兩點有無邊相連可在 constant time 得知。假設 R_NN 個點的一個 random graph,而 G_N 為依據 ε-biased sample space 所造出的 graph,Goldreich 與 Trevisan 證明了底下事實:

| Pr[M^(G_N) (N) = 1] - Pr[M^(R_N) (N) = 1] | is less than 0.1

簡單來講,就是說不夠多的 queries (i.e., o(N^2)),無法區別出 G_NR_N;亦即對於給定的 graphs G_NR_N,此 machine accept 他們的機率值差距非常小。

這式子和它的證明困擾了我許久。後來我發現原來是我漏掉了作者的一些敘述。作者給定一個合理的假設: M 可以丟一組 (或「一個」丟好幾次) 自己的 (公平的) 銅板,然後根據擲銅板的結果來對 oracle 做 query,並且每次 query 還能知道並參考前面的結果 (此即"adaptive")

M 擲銅板後所決定的 queries 會得到一組 "有邊 (1) 或沒邊 (0)" 的答案 (i.e., 一組 {0,1}-sequence)。如果 graph 為 R_N,則這些答案出現的機率是均等的。但是如果 graph 為 G_N,根據 ε-biased sample space 的定義與性質,這些「答案」出現的機率就會有一點偏差,但是偏差得十分有限。同樣一個 machine M,根據每一組 queries 的結果來決定要不要回答 accept。

a_i, where i = 1, 2, ..., 2^t, 表示每一種 t-query 的答案,且令 a_i 在 input graph 為 G 的條件下發生的機率為 p_G(i)。令 b_iM 在得到 a_i 後 output 為 accept 的機率。則 | Pr [ M^(G_N) (N) = 1 ] - Pr [ M^(R_N) (N) = 1 ] | 就可利用下面式子來估算:

|\sum_{i=1}^{2^t} [p_(G_N)(i) - p_(R_N)] * b_i | <= ε * 2^t

因為 paper 中把 ε 設定為 0.1 * 2^{-t},所以上式可以得到至多為 0.1。

我想,至少對於想要或正在讀這篇 paper 的人而言,這樣子應該是清楚了。不過 Trevisan 寫的 paper 一直都蠻困擾我的,到現在我問他的問題,他始終沒有回覆我。


(*) 參閱 Joseph Naor 與 Moni Naor 合著的 paper : "Small-bias sample space: efficient constructions and applications",發表於 1993 年 SIAM Journal on Computing, Vol. 22

No comments: