Thursday, July 31, 2008

Forward: 一天變出二十五小時 (25 hours a day)

http://www.cw.com.tw/article/index.jsp?id=34895

一天變出二十五小時 十五分鐘工作術

作者:張漢宜 出處:天下雜誌 399期 2008/06

重點摘要:浪費時間的四大元兇為
  • 考慮太多,優柔寡斷
  • 完美主義
  • 害怕失敗
  • 挑簡單、喜歡的先做

一樣的一天二十四小時,常嚷著說沒空的人,也許只是沒有抓到運用時間的技巧,十五分鐘工作術,幫助你做個效率達人。

Saturday, July 19, 2008

Axman pond (樵夫之泉)

http://www.youtube.com/watch?v=GRmfXZbmbg0




哆啦A夢影集裡面最有意思的一個。情節相當 KUSO。

話說真有這樣的東西的話,那我要寫篇 paper 投進去,看看女神會不會拿出一篇寫好的 STOC 等級 paper 出來。

Friday, July 18, 2008

Supervising a junior

學弟 Nick 今年七月要碩士班畢業口試,老師大概跟我提了一下論文內容,叫我跟 Nick 合作,把他的論文修改完以後,再看看要投稿到哪裡去。論文的主題是 maximum quartet consistency (MQC) 的 heuristic algorithms。老師對於 Nick 的研究結果很放心,所以交代我把論文的 presentation 寫好。感覺就像是我要賣一個產品,賣不賣不出去就全看我怎麼推銷。但是關於產品的內容呢?

Friday, July 11, 2008

Approximating the graph by empty graphs

今天下午跟 BarrosH 討論,對於 papers 裡常提到的底下這一句話,有一點小心得。

Note that the Regularity Lemma is only meaningful for dense graphs, because for sparse graphs, the density of edges between the pieces of the partition tends to 0.

因為一個 sparse graph 的邊不多,所以一旦把邊都集中在 partition 裡的 blocks 裡面,那 block 與 block 之間的邊就會非常少。把 block 用點來代表,如果一個 block-pair 為 dense (ε-)regular,則兩個對應的點就連上一條邊,這樣得到的圖形就是所謂的 regularity graph。如下圖所示, V = {a, b, c, d, e, f, g, h, i, j, k, l},可以 partition 成 3 個 blocks。




因為絕大部分的邊都集中在 blocks 裡面,所以 block-pairs 之間的 density 很低,所以形成的 regularity graph 非常有可能擁有極少的邊,當然 density 為 0 也滿足 regular pair 的條件 (非常低或非常高都很容易滿足 regular pair 的條件)。因此,我們很容易可以得到一個滿足 regularity 的 partition,以及一個對應的 regularity graph,亦即一個 (幾乎是) empty graph。Regularity lemma 重視的是 block pairs 之間的邊,所以一旦圖形不是 dense graph,威力就大打折扣。

另外,假設有 k 個 blocks,當然令它為一個 constant。每個 block 裡面會有 n/k 左右的點,所以去算一個 block pair 的 density,大概會有底下的結果:



所以說,當 n 夠大時,造出來的 regularity graph 是 empty graph,應該是沒有問題。果然,有討論真的有差。感謝 B 大的分享。

Tuesday, July 08, 2008

Giving a talk on the regularity lemma

今天下午花了大約一個小時,向 Peter, Stefan, Joachim, Alexander 以及綾珠介紹 Szemerédi's regularity lemma 以及利用它來檢測 triangle-freeness 的一個小小應用。(投影片在此)

一開始在 Szemerédi Theorem 那邊就花了一點時間,然後當我一提出 Terence Tao 關於質數有無窮多個任意長度的等差數列這個結果時, Peter 原本還不相信這有什麼好證的,但是大家討論了一會兒後,我才慢慢能進入正題。後來,光是讓大家熟悉 regular pairs 又花了一點時間。不過從這邊可以了解,他們做研究跟李校長一樣,都會把基本的定理「把玩」一番,然後幫助自己 (也幫了演講者) 更加了解定義相關的特性。接下來的 Regularity Lemma,他們一下子就抓到精神了。到了 Triangle Removal Lemma 那裡,我不對數字的計算多加著墨,只強調概念和直覺上為什麼 work 的理由,他們因此更能迅速了解。

結束了以後,每個人都向我表示感謝,其實我才要感謝他們用心聆聽我的演講。好家在,我那破破的英文還是可以讓人家懂。從今天的演講中,可以發現 Stefan 的確是很聰明,他能精準地抓到定義和定理的精神,所以經常聽他向 Peter 解釋當中的環環扣扣,覺得他真的很不簡單,可惜就是不走理論界。另外,這邊的學生對於理論界都還蠻有 sense 的,譬如說我一講到 primes 在整數上「應該」是蠻 dense 的,他們就知道 1, ..., N 當中質數的 density 大概是 1/log N,(可參考所謂的 PNT (prime number theorm),我記得之前好像有看過)。不會像我們好像都只對自己的問題比較熟悉,其他完全陌生或一無所知。

剛講完 regularity 應該只用在 dense graphs,回來就看到 survey 上面寫的 for sparse graphs 的 lemma。今天找時間再看一下。話說到底可不可以跟 Peter 擅長的領域搭上關係呢?目前還不知道。

Monday, July 07, 2008

Density of a regular pair is the average density of sub-pairs

一些關於 regular pairs 的性質。
給定一個圖 G,令 A, BG 中兩個互斥的頂點集。假設



分別為 AB 的 partitions。在此先考慮一個特殊的情況:



所以很容易地,我們可以得到

.................... (*)






亦即 (A,B) 的 density 等於 A, B 所有 subgraphs 形成的 "sub"-density 之平均值。更進一步地來說,可以考慮底下的定理 (即 Fact 1.2 in Komlós and Simonovits 在 1996 年的 survey):

Theorem: Given a bipartite graph with classes A and B, then for all integers k < |A| and l < |B|, we have



這一樣也是整體 density 等於所有同等大小 subsets 的 density 平均值。以上這些東西,paper 有時會出現。在這邊給個 remark 也好。

Thursday, July 03, 2008

Additive Combinatorics and Computer Science

從 BarrosH 那邊得到了以下資訊,感謝他的提供。

Additive Combinatorics and Computer Science.
Mini-Course: August 23-24 at Princeton University

主題包含:

  • Introduction and overview
  • Szemerédi regularity lemma and Szemerédi's theorem for k = 3
  • The sum-product theorem and its applications
  • Proof of the sum-product theorem
  • Proof of the regularity lemma
  • Szemerédi's theorem for k = 3: Roth's proof
  • Gowers uniformity norms and sketch of Gowers' proof of Szemerédi's theorem
  • Applications: Direct Product Theorems
  • Applications: PCPs and pseudorandomness

Also:
Luca Trevisan's Blog: in theory


Tuesday, July 01, 2008

Embedding Lemma & finding regular partitions of a graph

Theorem (Special form of Embedding Lemma).

Given , a graph R, and a positive integer m. Assume that |V(R)| = r and the maximum degree of R is Δ > 0.

Let us construct a graph G by
  1. replacing every vertex of R by m (independent) vertices, and
  2. replacing the edges of R with ε-regular pairs of density at least d.

If , then . In fact, the number of labelled copies of R in G is at least .

其實可以把 regularity 想像成一種「隨機性」。當 ε 的值愈小,regular pair 就愈「隨機」。更精確地來說,當兩個 vertex sets U, V 的 subsets A, B 儘管很小,但是它們的邊密度 (e(A,B)/|A||B|) 仍然可以與原來的邊密度 (e(U,V)/|U||V|) 十分相近。

這個定理給人的感覺,很有 Ramsey theorem 的味道。差別在於這邊是給予 regularity 一個上限,而 Ramsey-like theorem 則是給與圖形的頂點數一個下限。此外,embedding lemma 還能夠數算 labelled copies 的個數,感覺上又更強大了一點。

此外,如果把造 G 的第二點改成 complete bipartite graphs 而非先前的 "regular pairs",然後把這個另外造出的圖形叫做 G*, 那麼如果 HG* 的 subgraph,則 H 亦為 G 的 subgraph。這個變形的定理 (大致上) 就是有名的 "The Blow-up Lemma" (*)。

(*) Quotes of the Blow-up Lemma:
"... Regular pairs behave like complete bipartite graphs from the point of view of bounded-degree subgraphs. ..."


====================================================

Algorithmic version of the regularity lemma (Alon, Duke, Lefmann, Rödl and Yuster [FOCS'92]):
  • Finding ε-regular partitions of a graph can be done in polynomial time.
  • However, describe this partition to someone else, he or she cannot verify in polynomial time that this partition is really ε-regular.
也就是說,有多項式時間找出一個圖的 regular partition。如此一來,先前所說的 regular partition 的「存在性」都變成了「可建構性」 (constructive)。但是給定一個圖以及一個 partition,要檢驗這個 partition 是不是 regular 卻是一個 co-NP complete problem.



參考資料:
J. Komlós, A. Shokoufandeh, M. Simonovits, and E. Szemerédi: The regularity lemma and its applications in graph theory. Theoretical Aspects of Computer Science, Lecture Notes Comput. Sci., Vol. 2292, pp. 84--112, 2002.