Finite Playground

To verify is human; to prove, divine.


Leave a comment

A few interesting open problems

Advertisements


Leave a comment

Expander graphs (1)

最近在讀 “Expander graphs and their applications” by Hoory, Linial and Wigderson. 目前人在第三章, 但理解應該只有到第二章… 這是一篇寫得相當清楚的文章, 動機充足, 技術細節也寫得簡潔, 難怪別人也常引用它!

第一章提到 Expander 這種擁有某種 “特殊性質” 的圖被造出來的三個用途, 目前先嘗試的講其中一種, 也就是減少 random bits 的使用量. 考慮底下這樣的問題:

若有一個問題Q, 假設我們有一個演算法能在 poly-time 決定給定的 input 是不是在Q中, 若在的話我們有1/4的機率會答錯成不在, 而若不在的話一定不會答錯.
(注: 這樣的問題的集合稱作 RP, randomized poly-time, 其中1/4是亂定的, 只要小於1/2就可以)

請問若原先的演算法需要k個 random bits, 那若我們想將錯誤的機率1/4降到某個夠小的\epsilon(例如2^{-100}), 需要多少個 random bits?

最直接的想法, 就是將原先的演算法跑個d次, 這樣錯誤率就會降至(1/4)^d = 2^{-2d}. 在題目中我們令\epsilon = 2^{-100}, 因此d = 50. 這時, 我們需要d \cdot k = 50k個 random bits. Expander graph 厲害的地方, 就在於同樣重複執行了數次的演算法, 它仍然只需要k個 random bits!! (當然, 這裡用了一些骯髒的手段, 例如只有對於 input 長度夠大時才行)
這個演算法是由 Karp, Pippenger, Sipser 在 1985 年的論文
“A time-randomness tradeoff” 中提出來的.

我們先定義 (n,d)-expander 為一張圖G = (V,E),|V| = n, 而任意點v \in V都有d個鄰居在R中, 滿足底下的延展性質:

(expansion property):

|N(S)| \geq d \cdot |S|成立

對於所有V的子集S滿足|S| \leq \frac{n}{2}, 其中N(S)是指S在圖中鄰居的集合.

換句話說, expander graph 所擁有的特殊性質其實就是: 對於每個夠小的點子集, 它們的鄰居都很多! 當然第一個問題就是, 真的會有這麼好的圖嗎?
下面的引理保證了這件事.

Lemma. 對於夠大的(n,d),(n,d)-expander 存在.

因此, 我們可以利用這樣的圖來讓演算法的錯誤機率降低, 同時又不使用額外的 random bits. 令原先的演算法為M(x,r),x是 input, 而r是 random bits. 因此我們有M(x,r) = 0x不在Q中, 而有1/4的機率M(x,r) = 0xQ中. 固定一個xQ中, 我們把這種壞掉不好的r的集合取名叫

B = \{r \in \{0,1\}^k \mid M(x,r) = 0\}.

這時我們有的資訊很少, 若我們令n = 2^k, 先固定一個(n,d)-expanderG=(V,E), (n其實也就是所有長度為k的 random bits 的數量, 同時也是V的大小) 我們知道BV的一個子集, 而且B很小, 只有|B| \leq n/4.

我們可以想像演算法選了某一個r, 就像是從V中挑一個點一樣.
利用 expander 的延展性, 我們現在要從V的子集當中選出d個點, 讓演算法執行M(x,r_1), \ldots, M(x,r_d), 如果其中有任何一次它成功的回答M(x,r_i) = 1, 我們就知道其實x是在Q中的. (因為如果不在, 演算法一定答0) 不然就還是回答x不在Q中.
怎麼選呢? 我們就從剛剛用k個 random bits 選出的V中的一點, 取它的d個鄰居!! (這就是省 random bits 的所在! 因為鄰居是固定的!)

這時答錯的機率有多少呢? 唯有當我們選到的r_1, \ldots, r_d通通都掉在B裡!
我們來算算這d個鄰居都在B中的機率: 令SV的子集合, 包含了所有點v使得N(v)都在B中; 換句話說,S = \{v \mid N(v) \subset B \}. 只要算出S的大小, 就是答錯的機率了:

d \cdot |S| \leq |N(S)| \leq |B| \leq \frac{n}{4},

所以, 我們有|S| \leq n/4d, 換句話說, 錯誤率只有1/4d!!!
回想剛剛的例子中\epsilon = 2^{-100}, 如果我們選d = 2^{100}/4, 一切就搞定了… 甚至更可怕的, 對於任意的\epsilon, 我們只要選一個鄰居夠多(d夠大) 的(n,d)-expander 就好了! 無怪乎 expander 是這樣強大的工具…

什麼? 你說減少 random bits 有什麼用? 哼哼… 請期待下集 (對不起我累了… 下次再打!)