expander | Finite Playground

最近在讀 “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) = 0$ 若 $x$ 不在 $Q$ 中, 而有 $1/4$ 的機率 $M(x,r) = 0$ 且 $x$ 在 $Q$ 中. 固定一個 $x$ 在 $Q$ 中, 我們把這種壞掉不好的 $r$ 的集合取名叫

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

這時我們有的資訊很少, 若我們令 $n = 2^k$ , 先固定一個 $(n,d)$ -expander $G=(V,E)$ , ( $n$ 其實也就是所有長度為 $k$ 的 random bits 的數量, 同時也是 $V$ 的大小) 我們知道 $B$ 是 $V$ 的一個子集, 而且 $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$ 中的機率: 令 $S$ 是 $V$ 的子集合, 包含了所有點 $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 有什麼用? 哼哼… 請期待下集 (對不起我累了… 下次再打!)

Finite Playground

To verify is human; to prove, divine.

Tag Archives: expander

A few interesting open problems

Expander graphs (1)