Finite Playground

To verify is human; to prove, divine.

Category Archives: News 新聞


by Leave a comment

MA-SETH is false

Ryan Williams just posted a new paper Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation on ECCC, in which he disproves the MA analog of the Strong Exponential Time Hypothesis (MA-SETH), which is motivated by the paper Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility by Carmosino, Gao, Impagliazzo, Mikhailin, Paturi, and Schneider, proving that assuming Nondeterministic Strong Exponential Time Hypothesis (NSETH) then some problems like 3SUM and APSP cannot be SETH-hard.

 


by Leave a comment

New improvement to fast matrix multiplication

最近花了許多時間讀資格考, 寫了不少筆記, 沒有時間寫網誌…  難得有新聞來寫一下!

Again the exponent for the fastest matrix multiplication algorithm is improved.  This time the magical number is 2.3728639, 0.0000630 better than Williams’ 2.3729269.  (Last time it goes from the famous CW bound 2.3754770 to Stothers’ 2.3736898 then to Williams’, a 0.0025501 improvement.)

Powers of Tensors and Fast Matrix Multiplication, François Le Gall, 2014.


by 3 Comments

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!! 實在是太不可思議了… 對隨機演算法或是圖論演算法有興趣的人, 這是個必看的結果!


by Leave a comment

NEXP do not have ACC0 circuits

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

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

\mathsf{NTIME}(2^n)不能用\mathsf{ACC}^0circuits – 也就是 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}之後, 最重大的結果!!


by 3 Comments

Vinay Deolalikar 證明了 P 不等於 NP?

二零一零年八月六日, 也許這將會成為一個重要的日子.

就在這一天, HP 實驗室的 Vinay Deolalikar 宣布了他解決了 P/NP 問題. 很不嚴謹的問題敘述如下:

是否所有能夠迅速檢查正確性的問題, 都能夠被迅速的計算?

P 代表著所以能夠被迅速計算 (行話來說, 就是指在多項式時間內) 的問題的集合, 而 NP 代表能夠被迅速檢查的問題的集合. 這問題屬於計算理論這門學問, 其中 P 在 NP 之中是個已知的結果. 幾十年來, 許多人投注心力於證明或反證這兩類問題是否一樣, 也有許多人宣稱他們證明, 反證, 甚至是說明這個問題無法解決, 直到目前為止都沒有一個令人接受的答案.

Vinay Deolalikar 是 HP 實驗室的研究員, 他曾經發表過資訊理論相關的論文, 以背景來看並非對問題的歷史和難度一無所知. 此外從論文的寫作來看, 是相當正經的, 也有最上層的證明簡述, 以及提供他對此證明正確的基本辯證, 經過相當的用心寫出, 希望能夠真正解決掉此世紀難題. 此外許多新觀念的引進, 增添了此證明的可信度, 即使沒有成功, 也給其他人多了許多繼續研究的方向.

Dick Lipton 在他的 blog 上面簡述了證明的大綱, 另外網路上還有一堆相關的討論, 希望在不久的將來, 就能知道這個證明的正確與否, 以及提供更清楚, 完整的證明方式.

我們這些小毛頭學生, 就等著看吧!