Finite Playground

To verify is human; to prove, divine.

Expander graphs (1)

Leave a comment

最近在讀 “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 有什麼用? 哼哼… 請期待下集 (對不起我累了… 下次再打!)

Author: hcsoso

Ph.D. student in the Department of Computer Science, University of Illinois at Urbana-Champaign.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s