Friday, May 30, 2008

Concerning monotone graph properties

今天我寫了封信給 Asaf Shapira:

Dear Professor Shapira,

I am a Ph.D. student in Taiwan. Recently I studied articles about property testing. I read your paper
  • EVERY MONOTONE GRAPH PROPERTY IS TESTABLE.
In this paper, you define that a graph property is monotone if it's closed under removal of edges and vertices. You mentioned that in Goldreich and Trevisan's paper, they define that the monotone graph property is only closed under removal of edges.

However, in Goldreich and Trevisan's paper, they define that a graph property is monotone if it's closed under edge-addition.
I think this is different from what you mentioned in your paper.
Consider connectivity for an example. If a graph is connected, then adding any new edge results a connected graph. Yet edge-deletion of a connected graph doesn't guarantee resulting another connected graph.

Thanks for your patience for reading this email.

Best regards,
Joseph

Wednesday, May 21, 2008

Trip to IWPEC (Part 6: May 18, 2008) - final

May 18, 2008:

前一天晚上很晚回來,打電話預約Shuttle Bus 也沒人接聽,請住宿接待處幫忙詢問也得不到肯定的答案,只好一大早五點多起床再打電話試試,好家在我還是成功約到了車。早上七點多我跟三位教授道別之後,收拾打包剩下的行李,九點半離開宿舍。


離開 UVic 之前,在校園裡拍到一隻四腳騰空的兔子

Trip to IWPEC (Part 5: May 17, 2008)

May 17, 2008:

這一天下午是 STOC 的 registration & reception,早上我們一大早就出發,目的地是 Sooke,聽說那裡有不錯的風景,沒有被破壞的大自然景觀。不過到了之後,老實說我覺得還好,相較之下,我覺得台灣的溪頭和阿里山也不錯啊。大夥兒花了大約 3~4 個小時的公車才到那附近,接著就是走了好幾個小時的路,穿越不少 trails。中間有一段路,我們跑去溪邊玩水,順便吃路上買的麵包當中餐。Rolf 和老闆玩起了打水瓢,他們的技巧都很好,打得超遠的,而我打出去頂多彈個兩、三下就沈了,好幾次我還差點跌倒。Peter 則是愜意地躺在石灘上小憩,露出他圓圓的大肚子。


Peter 的姿勢與我的影子



Trip to IWPEC (Part 4: May 16, 2008)

May 16, 2008:

這天早上,我陪 Rolf 一起去晨跑。可以感覺得到,他很多想法跟 Peter 不太一樣,不過人真的挺客氣的。我說我可以陪他一起去晨跑的時候,他看起來真的是很高興。沒想到跑步對我來講,變成了非常好的社交方式。跑完後,我又趕緊演練了兩次, Peter 還借了一支 pointer 給我,它有倒數計時的功能,翻頁的按鈕也不用找老半天。研討會提供的 pointer 常常會斷了連線,而且雷射光線很弱,按鈕也容易搞混,不知道上一頁還是下一頁該按哪裡。相較之下, Peter 借我用的那支就順手多了。衣著方面,我穿上老婆選的淺灰色格紋襯衫 (出發前,在 Aachen 家裡還跟房東借熨斗燙過),搭配黑色牛仔褲,老師本來還想借我一件襯衫穿,不過我想穿上老婆選的襯衫,感覺心情比較篤定。

Trip to IWPEC (Part 3: May 15, 2008)

May 15, 2008:
接下來研討會的正式兩天,我們都有早餐可以吃,都是一些麵包和蛋糕,飲料有牛奶、熱茶和咖啡。吃不完的,就留到 Coffee break 再吃。與會的人數,應該不到 30 個,感覺上真的是個小小的國際研討會,不過有很多很厲害很有名的大頭在,譬如 Jianer Chen, Hans Bodlaender (Ton Kloks 的指導教授), Michael Fellows (聽說在 15 號這一天,他跑去衝浪了), Erik D. Demaine (來自 MIT,小小年紀已經常常受邀成為 invited speaker 了),以及 "Invitation to Fixed-Parameter Algorithms" 這本書的作者 Rolf Niedermeier。聽了一些演講後,心裡頭有點挫折,因為我對 parameterized complexity 真的不熟,像是 W[t]-hardness ,不管是 logic 還是 algorithmic 的觀點,對我來講都很陌生。老闆說,我要多看 papers,多拓展自己的研究視野,這樣才不會跟國際研究脫軌。其實我也想啊,只是我怕老闆覺得我都沒有在想問題,所以才停在現在的那個問題打轉。


寬敞的演講大廳 (這次 IWPEC 只有一個 section)

Trip to IWPEC (Part 2: May 14, 2008)

May 14, 2008:

14 號這天是註冊日 (registration),program 裡也只有註冊這件事。Peter 這天早上五點就起床,因為我住他隔壁,也跟著提早起床準備一下 16 號要報告的演講稿。他蠻衰的,特地帶了一台 Notebook 來這邊想上網,結果網路卡好像壞了,學校的無線網路他也不能用,所以只好經常跑過來跟我借電腦,用 Skype 跟他的家人聯絡。老實說,我帶來的電腦也是他之前借我的,我說要給他用他又說不要,太客氣了。

這天早上,為了讓老闆多休息一會兒,我跟兩位德國教授一起到外面晃晃,還到附近的海灘看看海。說到 Peter 和 Rolf,他們曾經在 München 在同一間辦公室共事一年,感情好的不得了。這一天我忘了因為聊到什麼事情,Peter 跑去勒住 Rolf 的脖子,讓我嚇了一大跳。看起來感情真的是很好。幾乎每件事情他們都要鬥嘴,有一次 Peter 在廁所,不知道聽到 Rolf 講了什麼話,突然開門喊著 "I don't think so." 有時覺得聽他們鬥嘴,還可以訓練自己的邏輯思考,老實說蠻過癮的。

這張是誰拍的呢?

Trip to IWPEC (Part 1: May 13, 2008)

International Workshop on Exact and Parameterized Computation
Time: May 14-16, 2008
Place: Victoria (British Columbia), Canada

Before the conference

我十分幸運,能夠參加這一次的 IWPEC。為了省錢,約莫一個月前就請我們親愛的秘書 Birgit 幫我訂機票。今年的STOC 也在 Victoria B. C. 舉辦,時間為 May 17-20,剛好緊接在 IWPEC 之後,所以老闆和 Peter 都想順便參加。我的加拿大簽證下來的有點慢,所以等到 Birgit 要幫我訂機票的時候,我的機票就比先前貴了400 歐元左右。為了錯開我的結婚紀念日,也避開適逢週末的 May 16-17 這兩天,所以 Birgit 幫我訂了從 May 13 凌晨出發,而 May 19 下午回來的來回機票。這段日子裡,我得放老婆一個人在家,還會跟三個教授一起生活 (老闆、 Peter Rossmanith、 Rolf Niedermeier),說起來蠻辛苦的。

加拿大幣與美金大約是 1 : 1,Victoria 那裡的氣溫跟 Aachen 比起來不會差很多,只是一開始去的前幾天有比較冷一點,大概只有攝氏 8 到 17 度,不過氣象預報說到了 16 號那天中午,氣溫會爬升至 30 度。 May 16 剛好就是我要報告的那一天,我想到時帥氣的短袖就可以派上用場了。