Wednesday, October 22, 2008

Research discussion today

其實我原本可以延至下週或更久之後才報告,但是就這麼一念之差,讓進度快了一個禮拜。這讓我體認某些時間點的關鍵性,該拼時不得不拼。

因為我已經習慣早上起床晨跑,所以今天有足夠的意志力在六點前起床,趕工尚未完工的投影片。我所報告的 paper 是 Alon 與 Krivelevich 在 2002 年寫的 "Testing k-Colorability",不過我只針對 paper 裡頭的第四章 (k > 2) 的部份來準備。因為我使用 Beamer 的關係,投影片頁數多達 90 頁,但是只相當於 ppt 的 30 頁左右。

因為 Ton Kloks 跟我提過他想來聽我的演講,所以在早上十點整左右投影片一完工,就請 Ling-Ju 幫忙叫他來參加我們的 group meeting。有一陣子沒有練習用英文演講的我,今天講起來還算是很順暢。不過,投影片還是熱騰騰的,我也沒有把它們好好順過一次,以致 Ton 與老師在某些地方不甚了解。尤其是 ε-far from k-colorable 與 colorless or restricting vertices 數目的關係,是老師一直很 care 的地方。這裡所倚賴的理論根據就是 Claim 4.1,講的是 violating edges (違反 k-coloring 的邊) 數目的上限。從這個事實可以接著導出 colorless vertices 與 restricting vertices 的下限。因為時間的關係,我沒有講述怎麼利用一個 auxiliary tree 來分析這個 testing algorithm 的 query complexity 以及 error probability 上限。

中午我們幾個學生和 Ton 一齊用餐,Ton 提出了一些想法,主要是從 square of a graph 的觀點,我覺得是不錯的點子!但是目前想起來似乎覺得有一點問題尚待釐清。下午接近五點的時候,老師找我下來一起討論這篇 paper。我們兩個人就這樣順著 paper 看,有問題就立刻討論。第一次跟老師「一起看 paper」,有點小感動。我想,老師應該是有抓住了演算法和分析的精神。我個人認為,這篇 paper 雖然有一些 typos,但是大致上還蠻精彩的,也不算難懂。不曉得老師的感覺怎麼樣。Ton 也會找時間讀這篇 paper,也許我們有機會做出一些結果出來也說不一定。

No comments: