Chicken's Finite Playground

Maximum matching in general graphs

首先, FOCS ’11 的 accepted paper list 出來(好幾天)了. 有 pdf 的版本在此. 今年有許多圖論演算法的論文在其中, 很多令人振奮的好結果!

今天想要來講一篇新出爐的, 一個令人驚訝的圖論演算法結果! 我們都知道所謂的 Maximum matching 問題: 給定一張圖, 求上面最大的 matching 的大小. 這個問題在 bipartite graph 上有 Hopcroft-Karp 利用 augmenting path 的 $O(m\sqrt{n})$ 演算法. 這被 Micali-Vazirani 推廣到了 general graph 上, 改進了標準的 Edmonds 開花演算法. 在這之後 Mucha-Sankowski 利用 Gaussian Elimination 及矩陣相乘作到了 randomized $O(n^\omega)$ time.

前兩天, 來自印度資訊科技學院的 Jindal, Kochar 和 Pal 在 Arxiv 上公布了這篇 Maximum Matchings via Glauber Dynamics, 宣稱他們將 maximum matching in general graphs 改進到了 randomized $O(m\log^2 n)$ time, 是第一個 near linear-time 的演算法! 使用的技巧是最近正夯的 Glauber Dynamics, 分析稍微複雜, 但演算法卻是簡單的驚人!

RandMatching(G), G 為 n-node m-edge graph.
1. 令 $M_0$ 為任意 matching. 令 $p = 2^m$ .
2. 執行底下迴圈 $k=10m \log n$ 次, 迴圈參數為 $i$ :
　　2.1 隨機選取一個邊 $e$ .
　　2.2 令 $M'$ 有 $\frac{p}{1+p}$ 的機率是 $M_i \cup \{e\}$ , 有 $\frac{1}{1+p}$ 的機率是 $M_i \setminus \{e\}$ .
　　2.3 假如 $M'$ 是個 matching, 則令 $M_{i+1} = M'$ ; 不然就還是讓 $M_{i+1} = M_i$ .
3. 輸出 $M_k$ , 程式結束.

簡單來說, 根本就是隨便亂選邊, 然後隨機加進去或是拿掉, 然後作了夠多次之後就宣稱輸出的結果有很大的可能性就是一個 maximum matching!! 實在是太不可思議了… 對隨機演算法或是圖論演算法有興趣的人, 這是個必看的結果!

作者為hcsoso

2011 年 07 月 15 日 at 上午 11:19

張貼於News 新聞

標籤 algorithms, Glauber-dynamics, graph-algorithms, matching, randomized

Random stuff, 110629

with 4 comments

最近讀了不少東西, 但都沒有花時間寫下來… 實在是個不好的習慣 :S
趁現在作一些速記! 希望有機會寫成文章… 囧

Triangle detection
很久很久之前讀過的 triangle detection. 用到了弱化的 $\epsilon$ -net theorem.
結果: sub-cubic triangle detection 等價於 sub-cubic All-pair shortest path(!), 更 imply sub-cubic Boolean matrix multiplication(!!)
Additive spanner
學習組合最優化 (combinatorial optimization) 與計算幾何 (computational geometry). 首先接觸的是 additive spanner 問題; S. Baswana et al. 的論文可以當作不錯的 survey.
簡單的學了 additive 6-spanner 的構造, 精神上就是 clustering.
結果: 任何圖會有個 $O(n^{4/3})$ -size additive 6-spanner. Sublinear-size $(1+\epsilon)$ -multiplicative spanner 有多種構造法.
Geometric set cover
然後就開始碰 geometric hitting set problem. 讀了 On the Set Multi-Cover Problem in Geometric Settings, 把 set multi-cover 問題 reduce 到一般的 set cover, 得到一個 $O(\log \mathsf{opt})$ -approximation 演算法. 而 set cover 一般來說只有標準的 $O(\log n)$ -approximation, 利用 bounded VC-dimension 配上 $\epsilon$ -net theorem (又是它!) 可以得到上面的 bound.
而對於 maximum coverage problem, 標準的解是個 $1-1/e \approx 0.632$ -approximation. 想要解所謂的 maximum 2-coverage problem, 也就是要 maximize 被蓋到兩次以上的點; 因為要 optimize 的函數喪失了 submodular 的性質, 因此目前沒有任何不單純的 upper bound.
Girth on planar graphs
關於平面圖, 老師和我寫的 Computing the Girth of a Planar Graph in Linear Time 上了 COCOON’11. 一張圖的 girth 是指圖中最小圈的大小.
Minimum cut on planar graphs
最近這個問題被解到 $O(n \log\log n)$ time. 其中 C. Wulff-nilsen 用 r-division, multiple source shortest-path 與 fast Dijkstra 解掉了很多平面圖上的問題, 但經過近半年的嘗試, 似乎這是現在技巧的極限.
在 unweighted graph 上蛋蛋和我提出一個關於 planar distance preserver 的猜想, 不過仍然不知道怎麼處理.
Diameter on planar graphs
現在嘗試改解 diameter problem. 一張圖的 diameter 圖中最長的 shortest path 的長度. 在 general graph 上人們相信這跟 All-Pair shortest path 一樣難, 但在平面圖上 C. Wulff-nilsen 可以解到 $o(n^2)$ , 因此說不定比較容易. 還在熟悉 diameter 的性質當中!
Even/odd hole detection
努力的寫作 even hole detection 論文中, 目前的時間似乎是 $O(n^{10})$ . 總覺得分析越多結構結果會越好, 但論文複雜度就越高; 似乎是個可以很容易得到 lower bound 的問題? 但沒有看到人做過.
讀了 Odd Hole Recognition in Graphs of Bounded Clique Size, 技巧跟當初 P. Seymour et al. 的 even hole detection 差不多, 只是在 odd hole 上的結構較弱, 最主要的問題是 clique 大小可以很大!
然後讀了證明 odd hole through one node 是 NP-complete 的證明; 試著想要去掉那個一定要經過的 node, 還沒有完全看出問題所在. Odd hole detection 永遠會是目標之一!

(to be continued…)

作者為hcsoso

2011 年 06 月 29 日 at 下午 12:14

張貼於Post-it 速記

標籤 algorithms, survey

Linear algebra and Lagrange interpolation formula

with 2 comments

最近在重讀線性代數, 對這門科目有了些新的認識!
前幾天讀到 dual space and dual basis, 發現高中時整天在算它的行列式, 卻一直不知道有什麼用處的 Vandermonde 矩陣:

$\displaystyle{ A = \begin{bmatrix} \alpha_0^0 & \alpha_0^1 & \cdots & \alpha_0^n \\ \alpha_1^0 & \alpha_1^1 & \cdots & \alpha_1^n \\ \vdots & \vdots & & \vdots \\ \alpha_n^0 & \alpha_n^1 & \cdots & \alpha_n^n \end{bmatrix} }$ ,

突然變得非常清晰!

–

考慮一個體 $F$ 上的 $n+1$ 維向量空間 $V$ , 令 $V^* = L(V,F)$ 為其對偶空間, 也就是那些從 $V$ 打到 $F$ 的線性函數所形成的向量空間. 令 $B = (e_0,\ldots,e_n)$ 為 $V$ 的一基底, 則我們在 $V^*$ 中會有對偶基底 $B^* = (e^0,\ldots,e^n)$ , 滿足

$\displaystyle{ e^j e_i = [i = j] }$ ,

其中 $[i=j]$ 值為 $1$ 如果 $i=j$ , 不然就是 $0$ . 可以想像基底跟對偶基底只要是不同國 (不同 index) 就會 “相殺", 這樣就好想多了.

用一些例子來看這個對偶基底: 令 $F=\mathbb{C}$ 為複數, $V=F^{\leq n}[x]$ 為所有係數為複數的 $n$ 次多項式所形成的向量空間. (檢查!) 這時我們會發現 $V$ 的維度是 $n+1$ , 也就是說基底大小會是 $n+1$ . 按照我們對多項式的 “直覺", 應該會猜 $B = (x^0,\ldots,x^n)$ 是一組 $V$ 的基底. (的確如此!) 那麼跟它對應的對偶基底是誰呢? 應該要是那些能滿足相殺性質的線性函數. 令 $B^* = ([x^0],\ldots,[x^n])$ , 其中 $[x^i] : V \to F$ 是取多項式中 $x^i$ 項係數的函數(因此 $[x^i]\in V^*$ ); 也就是說對於某個 $V$ 中的多項式 $f(x) = \sum_{i=0}^n \beta_i x^i$ ,

$\displaystyle{ [x^i](\sum_{i=0}^n \beta_i x^i) = \beta_i }$ .

因此, $B$ 與 $B^*$ 滿足相殺性質, 所以取係數函數 $B^*$ 是 $B$ 的對偶基底.

–

而除了取係數函數, 我們還有什麼在 $V$ 上很自然的線性函數呢? 當然就是取值函數了: 我們隨便取 $n+1$ 個不一樣的複數 $(\alpha_0,\ldots,\alpha_n)$ , 令 $B_L^* = ([\alpha_0],\ldots,[\alpha_n])$ , 其中 $[\alpha_j] : V \to F$ 是將多項式中所有 $x$ 代入 $\alpha_j$ 的函數; 因此對於某個 $V$ 中的多項式 $f(x) = \sum_{i=0}^n \beta_i x^i$ ,

$\displaystyle{ [\alpha_j](f(x)) = [\alpha_j](\sum_{i=0}^n \beta_i x^i) = \sum_{i=0}^n \beta_i \alpha_j^i = f(\alpha_j) }$ .

我們可以證明 $B_L^*$ 是個 $V^*$ 中的基底. 那麼它的對偶基底應該要是誰呢? 為了要滿足相殺性質, 經過一陣努力後我們發現應該是底下這組多項式. 令 $B_L = (L_0(x),\ldots,L_n(x))$ , 其中

$\displaystyle{ L_i(x) = \prod_{j=0 \atop j \neq i}^n \frac{x-\alpha_j}{\alpha_i-\alpha_j} }$ .

我們稱這些多項式為 Lagrange 多項式. 它們擁有的性質, 正好就是當你將 $\alpha_i$ 帶入這些多項式時, 會滿足

$\displaystyle{ [\alpha_j]L_i(x) = L_i(\alpha_j) = [i = j] }$

這樣的相殺性質! 因此我們知道 Lagrange 多項式 $B_L$ 是取值函數 $B_L^*$ 的對偶基底.

等等!

我們要怎麼證明 Lagrange 多項式 $B_L$ 的確會是 $V$ 的一組基底呢? 他們不像 $B = (x^0,\ldots,x^n)$ 看起來這麼和藹可親; 不過, 根據對偶基底的性質, 我們有以下等式: 對於 $V$ 中的任意多項式 $f$ ,

$\displaystyle{ f = \sum_{i=0}^n (e^i f) e_i }$ .

因此在我們的例子中, 我們將 $f$ 依序代入所有 $B$ 基底中的 $x^j$ :

$\displaystyle{ x^j = \sum_{i=0}^n ([\alpha_i]x^j) L_i(x) = \sum_{i=0}^n \alpha_i^j L_i(x) }$ ,

我們發現這是一組線性方程, 也就是一個從 $B_L$ 到 $B$ 的線性變換. 將這個線性變換寫成矩陣的形式, 我們很驚訝的發現這個矩陣恰巧就是Vandermonde 矩陣!!

而我們高中時計算 Vandermonde 矩陣的行列式值不為零, 完全就是在說這個線性變換是個 $V$ 上的自同構映射 (automorphism), 而 $B_L$ 的的確確是個基底. 我們稱這組線性方程為 Lagrange 插值公式 (Lagrange interpolation formula), 它的用途在於能夠回答底下這個問題:

給定兩組 $n+1$ 個不一樣的複數 $(\alpha_0,\ldots,\alpha_n)$ 與 $(\beta_0,\ldots,\beta_n)$ , 求一個 $n$ 次多項式 $f$ 滿足 $f(\alpha_i) = \beta_i$ .

要怎麼得到這個多項式 $f$ 呢? 若是用基底 $B$ 來思考就會很困難, 但改用基底 $B_L$ , 很容易我們就可以看出令

$\displaystyle{ f(x) = \sum_{i=0}^n \beta_i L_i(x) }$

就行了.

–

原以為故事到這裡就告一段落了, 沒想到在看後面的矩陣對角化時, 前面說的事情可以帶來更新一層的感受… 待續!!

作者為hcsoso

2011 年 04 月 15 日 at 下午 4:07

張貼於Knowledge 新知

標籤 dual, linear-algebra

Discrepancy theory

leave a comment »

Let $(V,\mathcal{S})$ be a set system with $V = [n]$ and $\mathcal{S} \subseteq 2^{[n]}$ . A ±1-coloring is a mapping $\chi : [n] \to \{1,-1\}$ . The discrepancy of a set system $(V,\mathcal{S})$ is defined as

$\displaystyle{\text{disc}(S) = \min_{\chi} \{\max_{S \in \mathcal{S}} |\chi(S)|} \}$ ,

where $\chi(S) = \sum_{i \in S} \chi(i)$ .

General bounds:
- Spencer ’85, Six standard deviations suffice, $O(\sqrt{n \log (2|\mathcal{S}|/n)})$ .

If every element appears in at most $t$ sets,
- Beck-Fiala ’81, “Integer-making” theorems, $O(t)$ .
- Srinivasan ’97, Improving the discrepancy bound for sparse matrices: Better approximations for sparse lattice approximation problems, $O(\sqrt{t} \log n)$ .
- Banaszczyk ’98, Balancing vectors and Gaussian measures of n-dimensional convex bodies, $O(\sqrt{t \log n})$ .

Constructive bounds:
- Bansal ’10, Constructive algorithms for discrepancy minimization.

作者為hcsoso

2011 年 04 月 11 日 at 下午 2:55

張貼於Post-it 速記

標籤 combinatorics, discrepancy, survey

Shortest paths in graphs with integral weights

leave a comment »

發現每次寫文章都因為希望講完整, 寫的很長因此很花時間, 久了就開始懶了.
因此, 新增一個 “速記" 分類, 用來記錄一些想要寫下來但不想整理的東西 XDD

–

目前看到在 integral weights 上解 Shortest paths 的方法有:
Thorup ’03, directed graphs, $O(m + n \log\log n)$ , by integral priority queue
Thorup ’99, undirected graphs, $O(m)$ , by hierarchical bucketing.

如果有最大的邊重 C, 那麼
van Emde Boas ’77, $O(m \log\log C)$ ,
Thorup ’03, $O(m + n \log\log C)$ .

Survey: Zwick ’01.

作者為hcsoso

2011 年 04 月 06 日 at 下午 4:42

張貼於Post-it 速記

標籤 algorithms, graph, integral, Shortest-paths, survey

Isolation Lemma

leave a comment »

這段時間在學習一個好用的技巧 – 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}_i$ 為 $U$ 的子集所形成的集合. 令 $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.

作者為hcsoso

2010 年 12 月 03 日 at 下午 4:48

張貼於Knowledge 新知

標籤 complexity, isolation, randomized

NEXP do not have ACC0 circuits

leave a comment »

幾乎所有重要的 Complexity Theorists 的部落格上都有這條新聞…

簡單來說, Ryan Williams 在 11/8 證明了關於 circuit lower bound 的新結果:

$\mathsf{NTIME}(2^n)$ 不能用 $\mathsf{ACC}^0$ circuits – 也就是 constant-depth, poly-size circuits with AND, OR, NOT, and Mod_m gates for any m 解掉.

這個結果有多大呢? 說大也不大, 因為人們相信就連 $\mathsf{NP}$ – 比 $\mathsf{NTIME}(2^n)$ 小太多的問題集合都不可能被 poly-size circuits – 比 $\mathsf{ACC}^0$ 大太多的 circuits 解掉. 換句話說, 離 $\mathsf{P} \neq \mathsf{NP}$ 還有很遠.

可是那又如何? 這可是一個新的 lower bound 結果! 上過 complexity 就知道 lower bounds 有多麼難得到… 在 Ryan Williams 之前, 我們連 $\mathsf{NTIME}(2^n)$ 能不能用 constant-depth, poly-size circuits with Mod_6 gates (沒有 AND 跟 OR!!) 解掉都不知道!!

另外, 它使用的技巧也很符合之前 Ketan Mulmuley 提出的 GCT 計畫中, 用 “證明上界" 來 “證明下界" 的概念. 在這篇突破性的論文中有使用到 Ryan 自己在 STOC ’10 中的論文 “Improving exhaustive search implies superpolynomial lower bounds“. 這使得這個方向的研究又再一次活過來了, 尤其是當有二三十年 circuit lower bound 沒有新的眾大突破結果下, 大家慢慢對 circuits 失去信心時…

有興趣的除了看上面的網誌介紹之外, 趕緊看看 Ryan Williams 的論文, 這應該是繼 Reingold 的 undirected reachability in $\mathsf{L}$ 之後, 最重大的結果!!

作者為hcsoso

2010 年 11 月 10 日 at 上午 9:37

張貼於News 新聞

標籤 acc0, circuit, complexity, lowerbound, nexp

Chicken's Finite Playground

Maximum matching in general graphs

Random stuff, 110629

Linear algebra and Lagrange interpolation formula

Discrepancy theory

Shortest paths in graphs with integral weights

Isolation Lemma

NEXP do not have ACC0 circuits

近期文章

分類

標籤

TCS Stack Exchange

其它

Follow “Chicken's Finite Playground”