Finite Playground

To verify is human; to prove, divine.

Isolation Lemma

Leave a comment

Isolation

這段時間在學習一個好用的技巧 – Isolation Lemma. 當我們需要在一個圖中找到特定的結構 (例如一個 perfect matching), 有時直接去找不是那麼容易; 藉由孤立 (isolation) 出某一個特定的 minimum weighted matching, 我們就能很快的找到它. 最有名的使用就是在 [MVV87] 中 Mulmuley, Vazirani 和 Vazirani (你沒看錯) 藉由證明了最初 Isolation Lemma 的雛形而得到的 perfect matching\mathsf{NC}(平行) 演算法.

在此我們介紹兩種不同的改良版: 一種是後來被 [RA00] 使用, Reinhardt 和 Allender 證明了\mathsf{NL/poly} = \mathsf{UL/poly}; 此種方法的特點是得到的 bound 很好, 但是是非建構式的. 而另一種類似 hash 的方式則是被 [CRS93] 使用, 改進了當初 [MVV87] 的演算法而得的\mathsf{NC^2}perfect matching 演算法; 後面這種方法 weight 是建構式的, 可以直覺的看出為何它能夠把所有東西分開, 但是要用到少許的 randomization. (嚴格來說, 我們真正要使用第一種方式時, 還是有 randomized 的精神在裡頭.)

首先我們來看第一個形式的 Isolation Lemma.

Theorem 1.U為一大小為n的集合, 而\mathcal{F}_1, \ldots, \mathcal{F}_m為一族非空集合, 其中每一\mathcal{F}_iU的子集所形成的集合. 令d為重量的上限, 而W為所有重量不超過d的重量函數w: U \rightarrow [d]^n形成的集合. 若我們給定一參數0 < \alpha < 1使得\alpha > mn/d, 則至少有(1-\alpha)|W|的重量函數會使得每個\mathcal{F}_1, \ldots, \mathcal{F}_m中正好都只有一個最小重量的U子集.

看起來很複雜. 我們令m=1, d=2n\alpha = 1/2來觀察這個定理看看.

Theorem 1′.U為一大小為n的集合, 而\mathcal{F}為一非空集合, \mathcal{F}中每一元素為U的子集. 均勻獨立的在U上隨機給定[2n]內的重量. 則至少有1/2的機率會使得\mathcal{F}中正好只有一個最小重量的U子集.

這樣就好懂多了; 藉由隨機給定一些不大的重量, 很容易能夠使得\mathcal{F}中有個最小元素被孤立出來. 如果不要限制重量的大小, 這其實不是很困難; 只要對U中的元素u_1, \ldots, u_n分別給予重量2^1, \ldots, 2^n就行了. 不難根據二進位表示看出U中的元素都會有不同的重量. 重點在於, 這樣的重量是指數成長的, 而多數演算法的應用只能限制在多項式成長率下. 這時藉由一點點的隨機性, 就能夠達成這樣的目標, 這是 Isolation Lemma 的厲害之處!

來看一個實際的例子好了. 在 [RA00] 的證明當中, 他們用 Isolation Lemma 孤立出圖中某兩點之間的某條路徑. 因為對任意圖來說兩點間的路徑最多會有 exponential 那麼多, 所以我們需要借助 Isolation Lemma.

[p]為圖中的點集, U為圖中的邊集, \mathcal{F}_i為點1到點i所有路徑的集合. (注意我們將路徑視為邊集的子集.) 因為|U| = n = p(p-1)(有向邊), 我們令m=p, \alpha = 1/2, d=2p^3 > mn/\alpha. 因此根據 Theorem 1, 我們可以證明底下的推論:

Corollary.G為一p點有向圖, 而W為所有重量函數w: E(G) \rightarrow [2p^3]^n形成的集合. 則至少有|W|/2的重量函數會使得對於所有i, 點1到點i的最小重量路徑是唯一的.

為什麼需要這麼多的重量函數呢? 因為我們可以藉此證出更厲害的推論:

Corollary.W為所有重量函數w: E(G) \rightarrow [2p^3]^n形成的集合. 則存在w_1, \ldots, w_{p^2} \in W個重量函數會使得對於所有p點有向圖G, 一定有一個w_k使得在G種任意點1到點i的最小重量路徑是唯一的.

Proof. 對任意一張圖, p^2個重量函數都無法估立出最短路徑的機率是2^{-p^2}. 而p個點的有向圖共有2^n = 2^{p(p-1)}個, 因此p^2個重量函數都無法孤立出某一張p點有向圖的最短路徑的機率是

2^{-p^2} \cdot s^{p(p-1)} < 1,

因此存在某個重量函數不管什麼樣的p點有向圖都能夠孤立出其最短路徑. \Box

注意後面這個推論的重點: 那p^2個重量函數是對所有p點的有向圖都適用的, 因此我們可以把這些重量函數事先寫進程式當中, 每當輸入一個圖我們就拿其中一個重量函數來孤立出最短路徑. 如果不使用這種方式, 我們就要在程式執行過程中隨機的產生一些重量函數, 給定了一個圖, 我們需要

n\log p = O(p^2 \log p)

個 random bits 來產生一組重量函數.

接下來我們來看第二種方法.

前面提到如果不限制重量的大小, 只要對U中的元素給予重量2^1, \ldots, 2^n就好了. 第二個方法利用中國剩餘定理很輕易的將重量作一些改變而壓在多項式大小, 因此這樣的方法式建構式的. 我們回到只有一個\mathcal{F}的狀況, 這次我們利用\mathcal{F}內子集的數量來減少 random bits 的使用.

Theorem 2.U為一大小為n的集合, 而\mathcal{F}為一非空集合, \mathcal{F}中每一元素為U的子集. 存在一種使用O(\log|F| + \log n)個 random bits 的方式在U上給定[n^7]內的重量, 使得至少有1/4的機率會使得\mathcal{F}中正好只有一個最小重量的U子集.

最糟糕的狀況下|F| = 2^n, 因此使用的 random bits 會是O(n + \log n), 比前一種方法好; 當|F|更小的時候 (如|F|是多項式大小), 我們甚至只需要至多$latex O(\log n)$ bits 就夠了. 完整的證明請見 [CRS93]. 不過事實上如果|F|只有多項式大小, 我們其實可以連 random 都不要用! 這在 [PTV10] 裡被拿來用以證明\mathsf{RFewL} \subseteq \mathsf{UL}, 管它這兩個莫名其妙的東西是什麼.

Theorem 2′.U為一大小為n的集合, 而\mathcal{F}中有至多f(n) = O(n^c)U的子集S_1, \ldots, S_{f(n)}. 存在一種在U上給定多項式大小的重量, 使得\mathcal{F}中正好只有一個最小重量的U子集.

Proof. 首先我們給U中的每個元素u_i重量2^i. 然後我們來看底下這個多項式:

\Delta = \prod_{1 \leq i < j \leq f(n)} (w(S_i) - w(S_j)),

這個多項式的特色就是: 當重量函數w能讓所有\mathcal{F}中的元素重量都不一樣時, 這個判別式\Delta就會不為零. \Delta值的範圍會是\delta = (2^{n+1})^{f^2(n)}. 因此我們選出從2開始的s個質數p_1, \ldots, p_s, 使得它們相乘超過\delta = (2^{n+1})^{f^2(n)}. 換句話說,

\Delta \neq 0 \mod \prod_{i=1}^s p_i.

根據質數定理,

\log \prod_{i = 1}^s p_i = s + o(s) > \log \delta = (n+1)f^2(n),

f(n) = O(n^c)時我們只要有s = n^{2c+1}就夠了. 這時中國剩餘定理告訴我們, 因為\Delta \neq 0 \mod \prod_{i=1}^s p_i, 所以一定有一個p_i使得\Delta \neq 0 \mod p_i. 最後我們只要令新的重量函數為w^*(S) = w(S) \mod p_i就行了, 根據對質數大小的估計,

p_i \leq p_s \leq s\log s \leq n^{2c+2},

因此這個重量函數只有多項式的大小而已. 因為\Delta \neq 0 \mod p_i, 所有\mathcal{F}中的元素重量都不一樣, 滿足我們對定理的需求. \Box

最後有一些後記. Isolation Lemma 使用上需要 randomized, 因為\mathcal{F}在最糟的狀況下會有2^n個元素, 因此完全的 derandomized 是不可能的. 不過針對\mathcal{F}的特性 (例如前面舉的最短路徑的例子), 有些人致力於 derandomize 相關的結果, 也有不少成果. 希望未來能看到 Isolation Lemma 更多的應用!

References.
[MVV87] Matching is as easy as matrix inversion. K. Mulmuley, U. Vazirani and V. Vazirani.
[CRS93] Randomness-optimal unique element isolation, with applications to perfect matching and related problems. S. Chari, P. Rohatgi and A. Srinivasan.
[RA00] Making nondeterminism unambiguous. K. Reinhardt and E. Allender.
[PTV10] On the power of unambiguity in logspace. A. pavan, R. Tewari and N. V. Vinodchandran.

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