Monday, December 29, 2008

Mark & Eva's wedding party

這禮拜天是 Mark & Eva 的結婚喜宴的大日子,因為馬克是我在德國同甘共苦的愛人,當然要北上赴宴去給他捧場一下啦!

2007年秋季班三明治學員再度聚首 (大家都畢業或是快畢業了 @@)


The schedule of a normal day (一天行程)

最近已經不只一個人問過我怎麼安排一天的時間了,所以乾脆把我的行程貼出來跟大家分享。不過,我過的不是正常人的生活,可以說是宅男加強版。

  • 06:00-07:00 Get up + running (起床 + 晨跑)
  • 07:00-07:45 Breakfast time (早餐時間)
  • 08:00-11:30 Research or TA jobs @dorm (忙研究或助教)
  • 11:30-12:30 Rest + lunch (休息 + 午餐)
  • 12:30-01:00 Taking a nap (睡午覺)
  • 13:30-18:00 Research or TA jobs @dorm/office (忙研究或助教)
  • 18:00-19:30 Running (跑步)
  • 19:30-20:30 Shower + dinner (淋浴完吃晚餐)
  • 20:45-23:30 Research or TA jobs (忙研究或助教)
  • before 23:59 Go to bed (晚安)

這樣一天的工作時間大約 10-12 小時,重要的是效率很高。平時除了跑步以外,有沒有什麼休閒活動?答案是沒有 (如果陪老婆不算的話)。對我來講,跑步雖然有時後會很累,但是精神上的抒壓效果很好。前一陣子,我把自己逼的太緊,無時無刻都沒辦法停下來思考問題,潛意識裡好像認為休息是一種罪過一樣,呼吸的時候還會覺得胸口很緊。直到後來逼迫自己放鬆,同時盡量在慢跑不想工作的事情,幾天過後慢慢就好了。如果在工作當中覺得累了,就聽一些音樂放鬆一下。或者轉移注意力,看一些新聞,可以的話,就看一些 BBC 或 N. Y. Times 的新聞,不過以半小時為限。另外,週末的時間,對我而言就像過幾年出現閏年的調整一樣,讓我在陪伴老婆的時間當中消除剩餘的壓力,不過這也只限於她下班的時候,通常我週末是不可能完全休息的,週末的工作時間還是有大約 8 小時左右。

說不定有人覺得這樣的生活很乏味,有時候我連午餐都只是走到離宿舍不到 100 公尺的餐廳用餐,吃完立刻回來做事。所以有時候一整天就這樣忙忙忙,不知不覺就天黑了,頓時會感覺自己像是一個一直宅在宿舍的宅男一樣。其實生活很規律,就像當兵一樣,感覺也不錯啊。效率又高,對身體健康也好。

Exercises for randomized algorithms

我是一個奇怪的助教。老師希望我先把習題改完,我前一陣子卻把時間花在寫解答上面。其實,除了要批改作業,我也有點想加強這方面的功力,然後,想充實一個之前搞過的網頁

現在的 Exercises 與參考解答如下:
  • Events and probability [pdf]
  • Discrete random variables and expectation [pdf]
  • Moments and deviations [pdf]
  • The Chernoff bounds [pdf]
  • Balls, bins, and random graphs [pdf]
  • The probabilistic method [pdf]

這樣子其實自己有一點小小的成就感。只是期盼老師不要生氣。現在該繼續忙其他重要的事情了!

P.S.: 作業已於今日下午全部批改完畢。還沒繳交的同學還可以補交喔!(啾咪 >_^)

Tuesday, December 16, 2008

A surprising birthday party

Birthday party at December 15, 2009.

在與老婆逛完安平附近景點,順便吃了好吃的銀波布丁後 (詳情),我依約到嘉義與學弟妹碰面,一齊慶祝 Ling-Ju 的生日。用餐的地點是嘉義民雄的喜多郎火鍋,火鍋的消費價格為 NT. 260-280 之間,算是很划算,吃得超飽。就在大家都吃飽了的時候,突然餐廳的燈光全都暗掉,出現生日蛋糕,這個梗很好用,每次都很令人驚喜。只是沒想到,這一次我也是主角之一。


大合照
(左起: 顯如,阿哲,武雄學長,怡均,我,
聖全,基復,綾珠,天立,曉函和沇嬴)

Monday, December 08, 2008

I'm 29 years old now

上禮拜五是我的 29 歲生日,按照慣例,老一輩的人都叫我講自己 30 歲了,不可以用 "29" 這個數字。對於實事求是的我來講 (好吧,也許我用詞誇張了),我怎麼能接受莫名其妙地多長一歲呢?

對我來講,慶祝生日最好的方式,就是去大吃一頓。這幾天比較冷,我們選擇到吃到飽的火鍋店用餐,才剛到門口我就口水直流。當天晚上,我有如蝗蟲過境般地掃過美味的牛肉片和許多新鮮蔬菜,真的是又撐又爽快!藉這個機會,也多少把該補充的營養也補一些回來。

一眨眼已經 29 歲了......哎呀,感覺有很多壓力在肩上,經濟壓力、結婚帶來的家庭壓力、生養後代的壓力 (很多人都說要的話就趕快 XD) 等等。 要解決這些壓力的最好辦法就是趕快畢業。要趕快畢業就要趕快衝 paper,而要衝 paper 就得趕快把手邊這一篇 testing algorithm 改好,要改 paper 的同時還得兼顧助教的工作以及新一期的國科會計畫申請書,......。總之,林林總總的事情一大堆,也慢慢能體會為什麼 Turing 要跑那麼快了,為了要甩掉壓力嗎?


壓力很多很大,就會讓我忍不住回想起先前在德國的悠閒生活,過得真的是很快樂又充實。每天只要管做研究和採買生活用品就好,現在的雜事相對就比較多。現在有時早上起床我睜開眼睛,彷彿感覺到自己還在德國,走到客廳還可以看到窗外白茫茫的雪景。而走出門外,Josef Kunze 的家好像就在咫尺之遙,說不定還能碰巧遇到剛從 HIT 採買完回家的 Nadja 與他們的三個小朋友們。三國交界附近的樹林,似乎還歷歷在目,空氣還是一樣的新鮮。Josef 說得沒錯,我果然很想念那片樹林,還有在 Aachen 的生活。而回台灣前所去的根特,好像上禮拜才去過一樣,翻開相簿,當時的印象仍然十分深刻。


29 歲的我,面臨的挑戰很多。希望不管我年紀多大,都不要忘了自己打算走學術圈的初衷為何,也不要忘了自己的夢想。接下來的日子裡,希望趕快完成學業,早日藉由 Post-doc 的機會重返德國。

Monday, December 01, 2008

天兵老公的自白 (A slow-witted husband)

「什麼?你結婚了?!」
「什麼?你已經博五了?!」
有那麼值得驚訝嗎?不過第二點倒是蠻令我高興的,雖然馬尾常說我根本就是阿伯,不過我還是希望歲月在我身上留下的痕跡愈少愈好。

Thursday, November 13, 2008

Time Traveler (時光旅人)


時光旅人
Time Traveler: A Scientist's Personal Mission to Make Time Travel a Reality
- Dr. Ronald L. Mallett & Bruce Henderson
陳可崗 譯


感謝大魚推薦這本好書:「時光旅人」給我讀。不過我只有兩個禮拜不到的時間可以觀賞,因為學校有人預約這本書。

Friday, November 07, 2008

Reward for the competitions in CCU

靠!真的是太爽了!沒想到校運比賽還能有獎金可以拿。儘管數目不是很大,但是對於像我這樣熱愛競技運動的人來講,真的是非常大的鼓舞!
月底還有成功盃的校際田徑賽,我報名了 1500m 與 5000m。兩場在同一天比完,而且前幾名對手的等級又都是跟巴斯克差不多,所以想拼進前三名非常拼,但是依照我目前的狀況來說,我覺得有機會。1500m 目標可以放在 4:30,而 5000m 則是拼拼看能否跑進 17:50 內,這樣子的成績說不定有機會拼進前四名。

總之,要感謝系上的大力支持!雖然我一直為膝傷所苦,練跑的意念也有些動搖,但是現在想著為系為校爭光,跑步變得開始比較積極,也比較有動力了!

Wednesday, October 29, 2008

Writing solutions to exercises

我花了五天的時間去寫兩次作業的解答,不曉得是我太認真還是題目太多,總之忙到研究的題目都沒力沒時間去想。現在還有兩個作業等著我寫解答,以及一個 11/21 截止的期中報告。

然後看看學弟妹寫的錯誤答案,就會有股小朋友般的脾氣湧上腦門,想要直接在上面劈哩啪啦打幾個大叉撇掉(阿不過線上作業是要怎麼打叉呢)。話說回來,還是等心平氣和之後再來改作業比較好。

老婆的擔心是有道理的,如果忙個不停但是研究沒甚麼進展,也是白搭啊。只能說盡量再擠出點時間好好想問題吧。

附註:作業的題目和解答也順便放在之前我做的隨機演算法網頁上了,但是目前只有前兩章有答案。Ton 跟我說,這些題目做起來很無趣,因為大多只是單純套一套定義和定理下去跑一跑而已,不過對我來講,其實算是不錯的練習啦。

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,也許我們有機會做出一些結果出來也說不一定。

Tuesday, October 14, 2008

A tool for calculating branching numbers

之前在 RWTH-Aachen 時,我的研究室 Linux-PC 裡有一支小程式,可以計算一個 branching vector 對應的 branching number。回到台灣以後,那邊的帳號已經失效了,所以勢必得自己搞出一個計算 branching number 的程式。

其實去年年底之前,我就已經在某個程式裡寫出一個簡單計算 branching number 的 function 了。今天下午稍微改寫一下,就輕鬆得到看起來跟 Peter 那邊一模一樣的程式。程式碼可於這裡下載。其實算法很簡單,只不過是利用十分逼近法去求反轉特徵多項式的根值罷了。

在 Linux OS 底下,可以使用 gcc br.c -lm -o br 得到執行檔 br,然後將它移動至 /bin 底下,這樣子所有的使用者都可以在任何地方輸入 "br ",就可以得到 對應的 branching number 了。單純的 gcc 指令會出狀況,好像是因為 math.h 裡面沒有 pow() 這個函式的緣故。改用 gcc -lm 或是直接用 g++ 硬做都可以成功編譯。

至於使用方式呢?只要在 command line 輸入 br 和 branching vector 再按下 return 就可以了。比如說,輸入 "br 1 1 1 1",當然就是得到 4 啦,而輸入 "br 1 2" 就可以得到跟黃金比例的比值 1.61803401...。至於精準度,我只有設小數點後八位,應該是夠用了。

Sunday, October 12, 2008

A bash file for backup

以下是一個可以用來備份的 bash file



#!/bin/bash
# Program:
# Backup the tex file.
# History:
# 2008/10/12 Joseph C. C. Lin First release
# bash scrip name: backup.sh

file="paper"
tex=".tex"
day=`date +%G%m%d%H%M`
original="$file""$tex"
backup="$file""-""$day""$tex"
cp $original PAST/$backup
echo "Backup '$backup' to PAST"


這個 bash scrip 很好用!只要修改完 paper 後,執行 "sh backup.sh",它就會自動幫我把 paper.tex 備份到 PAST 資料夾去,而且檔名還會加上日期,譬如 "paper-200810121925.tex",說明這份文件是在 2008 年 10 月 12 日 19 點 25 分編寫後備份。

對於文件的備份和撰寫,使用 cvs (Concurrent Versions System) 應該是最好的方式,但是目前有遭遇一些問題,所以日後再說。

Saturday, October 04, 2008

Installing MPlayer in a Linux OS

參考資料來源:
http://www.linux.com/feature/37196

Linux 預設的影音播放軟體很難用,或者不知道哪裡才會用的上。所以,可以選擇安裝 MPlayer 與 Realplayer 這兩套好用的軟體。MPlayer 的參考安裝方式如下:

  1. 首先,前往 MPlayer download 網站,下載 MPlayer 的 source code (for example, MPlayer v1.0rc2 source: 檔名為 MPlayer-1.0rc2.tar.bz2)
  2. 下載完 source code 之後,接著解壓縮 .bz2 檔至某個資料夾,例如 temp
  3. 打開 terminal,進入 temp 資料夾中
  4. 執行以下指令
    ./configure --enable-gui
    make
    su (if you're not already root)
    make install

這樣子,MPlayer 就安裝好了!我之前想試經由 rpm 或 yum 的方式安裝,都沒辦法成功,現在終於 okay 了。至於 Realplayer,可以從這個 rpm 連結去下載安裝,簡單很多。

MPlayer 播放結果


Realplayer 播放結果 (德語第一課)

Thursday, September 18, 2008

Work in Linux again!!


因為思念德國的生活,所以我在辦公室 PC 上安裝了 VMware Workstation 6.0.5,在這個 virtual machine 上面灌了 Fedora Core 9,現在可以利用 Linux 寫文件、上網等等,輸入法則是在今天早上請基復幫我解決問題後安裝成功的。這篇文章就是在這個熱騰騰的 Linux OS 上面撰寫的。

記憶體我只分配了 512 MB 給它,硬碟空間只有 15GB,所以真的只是拿來寫報告、投影片和論文或是一些網誌文章而已,不然要硬碟要爆的話不難。

禮拜一正式接手計算機概論的總助教,據說事情非常非常多,是一件苦差事。不過從另外一個角度思考,倒是可以訓練我帶領一個 team 以及與小組溝通協調的能力,這些都是我缺乏的,說不定,還能練點程式。學弟妹看起來都很可靠,能力也強,也很聽話,或許今後的日子裡,大家都會有不少收穫吧。

話說回來,這樣子是為了日後「就業」而準備嗎?

Sunday, September 14, 2008

Too naive I am

我當時真是太天真了。

學弟在畢業前說的話,在他畢業後當然就可以不算數了。雖然照理說我也應該要自己來把這個 paper 完成,但是就是會覺得就是有那麼一點被欺騙的感覺。心裡有股很難原諒他的怨氣。

人都已經畢業了,也辦好離校手續了,誰還會鳥你論文哪裡要改,程式哪裡有問題?到最後還是得靠我自己來。

有時候,有些話真的是聽聽就好。當時我太天真了,把人家的客套話當真,讓我這時候更認清人性。該氣的人,反倒是自己。

Saturday, September 06, 2008

I'm back and something else....

經過一年,我終於回到台灣了。

從返台到 po 文的現在,我胖了三公斤以上,每天的排便也不若先前順暢,希望這只是短暫的現象。我和老婆趕快剪了清爽的髮型避暑,消暑的飲料不知道喝了多少杯。我們還和她弟妹們找了一天去唱歌,好久沒有唱歌,一口氣唱了五個小時的 KTV,聲帶的耐久力備受挑戰。

Tuesday, September 02, 2008

Baseball is not our national sport

分享一篇寫的不錯的文章:

「棒球不是台灣的國球」

延伸閱讀網誌:http://geppyxx.pixnet.net/blog/

Sunday, August 31, 2008

Wave Germany Goodbye

我們即將道別德國,返回台灣。在這裡待了這麼長一段時間,要離開這個可愛的地方總是會感到不捨。此刻的心情,就用 Simply Red 的一首歌: "Wave the Old World Goodbye" 來表達。



Thursday, August 28, 2008

關於張泰山藥檢事件 (A shameful affair with TPENOC)

延伸閱讀: 藥檢、皮球、張泰山

中華奧會秘書長陳國儀先生表示,希望中華職棒能配合國際棒球總會對於張泰山的禁賽處分,在中華職棒進行最新藥檢報告出爐前,別讓張泰山出場比賽 (新聞來源)。張泰山的從未拒絕藥檢,誤用禁藥也是為了有個孩子,於情於理都不應該怪罪於張泰山本人,有錯的應該是中華棒協及中華奧會。也因為他們的疏失,讓中華隊少了一名主炮,影響了接下來七場比賽。

老實說,我問過幾個德國友人,他們第一時間就認為禁藥不大可能會「誤用」,通常都是「故意」服用。所以我相信這個事件對張泰山和中華職棒的形象多少還是造成傷害。但是,中華棒協和中華奧會在藥檢上的紕漏 (參見此則新聞),卻要無辜的張泰山本人受罪,分明就是打自己家的小孩給別人看。張泰山繼續打中華職棒會影響棒球回奧運?真是笑話!真要管的話,先管管 MLB 吧!他們才是影響棒球重返奧運與否的關鍵。這些人只會在那裡透過媒體放話、互踢皮球,扯自己人後腿,真是笑話。「國恥」兩個字,不應該讓中華成棒代表隊承擔,應該送給棒協、中華奧會這些無能之人才對。

引述這篇文章的幾句話:
踢啊!踢死你們!
說什麼棒球是國球,我聽你們放屁。
踢皮球才是台灣的國球!

講的好!我們政府踢皮球真的是「世界級」的。對於政府、棒協、中華奧會,我們還能期待他們有什麼作為?光是不要扯自己人後腿就謝天謝地了。

話說鄉民發起籌劃「球魂基金會」與「金龍再現」的行動,還比較令人期待。希望這兩個活動能引起政府或企業的重視,甚至是資助,這樣我們的國球就有救了。

Monday, August 18, 2008

Politics & people

在目前的台灣,政治人物的表現跟人民的期望有極大的落差。當初選舉時所作的各種承諾,大多是為了跟敵對陣營的候選人有所區隔,或者根本就是謊言。等騙到了選票,從政時要做什麼事情完全基於政治的考量。就像最近一齣日劇「CHANGE」一樣,政治人物在政治上用盡心機,而人民的期望是什麼、需要的是什麼,只要對沒有利益可言。民意和政治,經常像兩道平行線。再加上媒體沒有照顧到社會公平與正義,人民只能無奈。說得漂亮的政黨政治,其實選誰、選什麼黨都一樣。

要怎麼改變目前的政局?很難。我相信大家慢慢會發現,政治充滿了謊言,我們不能天真地相信政治人物本身(譬如阿扁...唉),要相信的是制度和法律。不過,目前的制度和法律還不夠好,所以我們卻又仰賴可靠的政治人物帶來改變。但是我們目前的民意代表,又能代表多少民意?又或者,人民可否直接改變政局,而不用透過民意代表這一層?

最近 PTT 鄉民發起所謂的「大情蒐計畫」(詳見活動網頁) ,幫助中華成棒隊蒐及其它國家棒球隊球員的各項攻守數據,不靠政府、棒協。這項行動幾天前,大家還幫忙一人一信寄到行政院和總統府的信箱,希望引起政府的注意,讓中華成棒隊不用擔心球衣清洗的雜事,專心在球場上的表現。當然,中間還得感謝媒體的「助攻」,以上的行動都上了新聞版面,政府也不得不重視。看得出來,除了公投之外,人民還是有能力發揮他們的影響力。

關於體育這方面我突發奇想,如果我們能夠找出一些沒有政治背景,但是對目前體育十分有想法的學者或是教練、球評這些人,然後說服他們,大家一齊串連起來以選票幫助他們當選立委或議員,或許我們有機會發揮「鄉民」的影響力,改變我們這個國家目前的體育和教育問題。這些人可以像是曾文誠、蔡明里、鍾重彩這些人,他們對體育(尤其是棒球)有很好的見解和熱忱,但是對政治並無野心。不過真的只是我的突發奇想罷了。

Tuesday, August 12, 2008

People in Germany

從很多小事情上來看,德國人真的蠻粗枝大葉的,不會注意小細節。譬如說:

  • 突然接到 Josef 的電話,他約我要一起跑步,時間剛好是中午一點左右,我才剛吃完飯。
  • 老人上公車時,司機也是給它油門催下去,車上站立的乘客都差點跌倒,更不用說剛上車的老人會怎樣了。
  • 辦公室舀糖的小湯持直接用來攪拌剛泡的咖啡,然後再放回糖包裡。
  • 為了涼爽點,把門戶打開讓空氣對流,但是不把門卡好,結果走廊上辦公室的門一扇一扇「碰」一聲關上,他們也不以為意。
  • 開車的時候,看到綠燈就往前衝,不會擔心垂直方向的來車。 (ps: 某位德國友人說,If I die, at least I am right.)
其他的等老婆再跟我補充。感覺上,德國人真的是蠻粗枝大葉的。

Too high sometimes

有時候我講話會講到太 high,是我一個很嚴重的缺點。懂得在適當的時候內斂一些,才不會讓身邊的人感到困擾。還有,不確定的事情不要亂講。討論研究問題的時候是這樣,平時講話的時候也應該要這樣。

少說話多做事比較實在。要記得當我用手指著別人的時候,會同時有四隻手指頭指向自己。

摘錄自馬太福音
7:3 為甚麼看見你弟兄眼中有刺、卻不想自己眼中有梁木呢。
7:4 你自己眼中有梁木、怎能對你弟兄說、容我去掉你眼中的刺呢。
7:5 你這假冒為善的人、先去掉自己眼中的梁木、然後才能看得清楚、去掉你弟兄眼中的刺。


Sunday, August 10, 2008

Go Go Taiwan!!



昨天在科隆火車站的地下廣場裡面,看到一個準備播送奧運比賽的地方,那裡有塊告示板,列出奧運獎牌排行榜。赫然發現 Taiwan 的名稱和國旗,真的是非常爽。隔天看到新聞,才知道原來是女子四十八公斤級舉重項目由陳葦綾拿下銅牌(差點拿下銀牌)。

話說人在國外,能看到 Taiwan 這個字還有我們的國旗,真的是非常興奮!真希望在我有生之年,可以看到台灣變成一個名正言順的國家。

Taiwan Go Go Go~~ 奧運代表隊加油!中華成棒隊加油!


為中華隊奪金集氣

Thursday, August 07, 2008

What is sublinear?

有人搜尋 "what is sublinear time" 結果找到我的 blog 這邊來,看來可以發個文說明一下。

一般來講,如果 problem instance size 為 n,則 linear time 就是指 O(n)。但事實上, problem instance size 不見得就是 n,譬如一個 n 個點的圖形,如果是使用 adjacency matrix 來儲存,那麼 input size 就是 O(n^2)。所以說,假設 input size 為 O(f(n)),則 linear time 就是指 O(f(n)),這樣子也比較合理。

那什麼又是 sublinear time 呢?如果一個 problem 的 instance size 為 O(f(n)),則解決這個 problem 的演算法時間複雜度為 o(f(n)) ("little-o" of f(n)) 就稱為一個 sublinear time algorithm。little-o 的定義可以查演算法的課表,最簡單的定義就是利用 limitation 的方式。譬如 g(n) is sublinear of f(n) if 。所以如果 f(n) = n^2,則 O(nlog n)、 O(n) 都算 sublinear。

Wednesday, August 06, 2008

Hereditary and semihereditary graph properties

先看看底下關於 semihereditary graph property 的定義:
Definition. A graph property P is semihereditary if there exists a hereditary graph property H such that the following hold:

Any graph satisfying P also satisfies H.
There is a function M: (0,1) -> N, such that any graph G of size at least M(ε), which is far from satisfying P, contains an induced subgraph that does not satisfy H.

一開始看起來還蠻令人眼花撩亂的。事實上,semihereditary graph properties 是由 hereditary graph properties 所造出來的。造法就是對每一個 hereditary graph property 所代表的圖形集合「拿掉」其中一部分的圖。所以這也讓形成的「新集合」可能不會 "closed under taking induced subgraphs"。此外,那些 「ε-far from P 卻不包含不滿足 H 的 induced subgraph 」的圖形數目是「有限」的 (考慮 size at most M(ε) 的 graphs)。而對照一個 hereditary graph property P',ε-far from P' 的 G 「一定」含有不滿足 P' 的 induced subgraph。

根據上面的定義,每個 hereditary graph property 必定是 semihereditary (因為可以把 H 換成 P 自己)。根據 Alon 與 Shapira 在 2005 的結果 (also SICOMP 2008),一個 graph property 為 semihereditary 若且唯若它有一個 oblivious one-sided error testing algorithm。裡面的 "oblivious" 是指 testing algorithm 不需要知道 input graph 的 size。

Sunday, August 03, 2008

Testing colorability & hereditary graph properties

關於我論文計畫裡另一個(可能的)主題,是關於 colorability 的 testing。

雖說 monotone graph properties 與 hereditary graph properties 已經被證明為 testable,但是該結果應用了 Regularity Lemma,使得 query complexity 為深度 O(1/ε) 的 tower of 2's,遠比 exp(1/ε) 還恐怖。但是,這就像是當初演算法研究證明了某些問題為 polynomial time solvable 或 NP-hard 一樣,還是會有其它的方向可以走,譬如針對前者設計更有效率的 polynomial time (甚至 linear time) algorithms,針對後者則試圖找出 approximation algorithms 一樣。因此,就算前人已經利用了 Regularity Lemma 證明一個 property 為 testable,嘗試其他的分析或演算法來找出 poly(1/ε) 的 query complexity testers,都是可以走的方向。

現在手頭有些 papers 要先快速 view 過一遍,知道他們的精髓在哪裡,一面看一面再想關於我的問題還有什麼出路。

  • J. Komlós: Covering odd cycles. Combinatorica 17 (1997) 393-400.
  • N. Alon and M. Krevelevich: Testing k-colorability. SIAM J. Comput. 15 (2002) 211-227.
  • E. Fischer: Testing graphs for colorability properties. Random Struct. Alg. 25 (2005) 289-309.
  • N. Alon and A. Shapira: A characterization of the (natural) graph properties testable with one-sided error. SIAM J. Comput. 37 (2008) 1703-1727.
  • N. Alon and A. Shapira: A characterization of easily testable induced subgraphs. Comb., Probab. Comput. 15 (2006) 791-805.

property testing 的結果已經多到嚇死人了!如果寫篇 survey paper 應該是不錯的貢獻,可是作者的功力可得要有相當的程度才行。

除了硬著頭皮做 property testing 以外,當然也可以想一些相關的題目,譬如能不能應用到 approximation algorithms 或是 fixed-parameter algorithms 的設計之類的,都還可以再想想看。另外呢,Testing ρN-vertex coverability 在 dense graphs 上仍然是 open problem (testable or not) ? I think no.

Let us say P is the set of n-vertex graphs that have vertex cover less than k. Then P is a hereditary property.

最後,提醒自己一下,

A monotone graph property is also a hereditary graph property.
(舊文)

別老是搞不清楚了。

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.


Monday, June 30, 2008

Most degrees into a large set are large (the proof is worked out!)

Theorem: Let (A,B) be an ɛ-regular pair with density d. Then for any , we have




這個定理應該是挺直覺的,照理講不難證明才對。在 paper 裡只是一個 "fact"。在稍微思考之後,我自己寫了一個證明如下。
Proof:

Let be a constant. Let


and assume that

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

Hence we have
......................(1)

But , since (A,B) are ɛ-regular, we have
..........................(2)

(2) contradicts (1), therefore the theorem is then proved.



呃...好像真的不難...

其實直覺上來講,就是說 small degree 的 vertices 一旦太多,就會把邊的密度拉的太低,違反 regularity 的定義。證明的 trick 在於把這些 small degree 的點看成一個 subset,如此便滿足子集合的 size 大於 ɛ|A| 的條件,而形成稀疏的邊集。


定理出處:
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.


Thursday, June 26, 2008

A version of Szemerédi's theorem

給定兩個數 k (欲得之等差數列的長度) 和 d (density),其中 k 為正整數,d 為 (0, 1/2] 的實數。則存在一個 N = N(k,d),使得 {1, 2, ..., N} 當中每一個大小至少為 dN 的 subset 都會有一個長度為 k 的等差數列。

截至目前為止,N(k,d) 的 upper bound 和 lower bound 如下:



其中 C > 0.


參考資料:Wikipedia

++++++++++++++++++++++++++++++++++++

這個定理怎麼跟 regular partitions of graphs 扯上關係的,我還得再看看。我想這應該是 testing large graphs 的精髓所在。

Deutschland vs. Türkei (3:2)

昨天是歐洲盃足球賽四強賽程的第一場:土耳其對德國。勝者可以挺進週日的冠軍戰。不同於足球在台灣的乏人問津,歐洲人為了這次賽事瘋狂不已。某種程度上,足球賽就像是國家與國家之間的「戰爭」,也因此可以想見他們的激情程度,更勝於台灣的棒球瘋。
土耳其隊充滿奮戰精神,前幾場奇蹟般的逆轉秀演出讓他們跌破不少專家的眼鏡。德國隊則是除了預賽面對克羅埃西亞以 1:2 落敗以外,接下來的比賽當中漸入佳境,表現愈來愈好,尤其是上一場在大家都非常不看好的情況下,打敗勁敵葡萄牙隊,而另一場最具冠軍相的荷蘭隊卻意外敗給俄羅斯隊,也讓德國隊一下子變成冠軍的大熱門。

來到德國當然要入境隨俗,關心一下歐洲盃的賽況。德國境內有非常非常多的土耳其人,這也是他們不願在四強裡面遭遇土耳其隊的主要原因之一。老婆和我從 2006 年世界盃就支持德國隊 (因為帥哥多),所以雖然我們喜歡吃土耳其的 Döner kebab 和 Pizza,昨天的比賽就先暫時忘記這件事吧。Josef 叫我們好好待在家裡看轉撥,因為不管哪一方獲勝,街道上或許會因為過度激情而導致失控演出。

土耳其這一場比賽中,攻勢凌厲,讓德國隊門將生意興隆,反觀德國隊攻門次數相對少很多。土耳其隊在比賽開始 22 分鐘後率先進球,讓支持德國隊的老婆和我開始擔心起來。不過還好德國隊把握住難得的幾次機會,在土耳其進球約四分鐘後,由 Schweinsteiger 巧射入網。上半場兩對戰成 1:1 平手之後,比賽就開始陷入僵局。

下半場比賽在第 79 分鐘時,德國隊由帥哥 Klose 投鎚破網,土耳其門將衝出來檔也於事無補。不過接下來第 86 分鐘,德國隊因為後衛防守出現問題,導致門將 Lehmann 在準備接收土耳其的短傳時,球的行徑方向中途被改變,因而切入球網失分,比賽至此 2:2 平手。不過令人驚奇的是,在傷停補時的第 90 分鐘後,經由成功的小組配合,短小精幹的 Lahm 突破土耳其門將的防守 (猜錯邊),帥氣地起腳勁射破網。沒多久比賽結束的哨音響起, Lahm 在這一夜變成了德國的英雄。

其實朋友說德國隊這一場表現並不好,而且土耳其隊中有九名球員因為受傷或禁賽無法上陣,但這場比賽卻意外陷入膠著,幸好德國隊仍然險勝。德國隊的三個進球都很紮實,土耳其的那兩球則看起來比較 lucky。不過就攻勢上來講,土耳其是犀利很多,全靠德國的新門神守下來,不然不會只失兩球。今年,德國非常有機會拿下第四座歐足賽的金盃,就看俄羅斯和西班牙那一隊會出線了。

Wednesday, June 25, 2008

Strange reasons (似是而非的詭論)

  • 常言道:「早睡早起身體好」,就會有人堅持就算經常熬夜甚至通霄,身體還不是好得很。
  • 我經常勸朋友早點就寢,利用早上的時間做研究,他們會說晚上比較有效率,或者不熬夜趕不上進度。或者在某一、兩天早起,精神不好猛打瞌睡,便從此放棄早起的念頭。
  • 我勸朋友多運動,對身體好,又可以間接幫助思考,他們會說沒有時間做運動,或是運動完會很累沒辦法做事情,或者會說有哪些人沒有運動,身材還不是一樣好,身體一樣健康。
  • 大家都說職棒要辦二軍,結果會有人說沒有辦二軍的球隊不是還可以三連霸。
  • 練長跑需要基礎訓練,重視有氧跑和高里程,還有基礎肌力和基礎速度。一樣有人會說,某某人整年操間歇還不是超強,反正操到吐就練到了。然後說某某人做了所謂基礎訓練,成績不也是這樣而已。
  • 有時候看到平時不唸書,考試前熬夜通霄卻拿到不錯的高分,於是就覺得平時犧牲休閒時間認真學習的自己真是划不來。

不願意相信有根據的學理,只做沒有根據的堅持。不願等待長時間的結果,只著眼在短時間的成效。都是一些似是而非的詭論,卻有數不完的信奉者。

Monday, June 23, 2008

Progress? No progress?

號稱在做 property testing 的我,其實對這領域根本就不熟。稍微瞄了幾篇相關 testing graph properties 的 papers,發現最重要的東西其實還是圖形的「特性」,尤其是 regularity lemma,乃是精髓所在。做這個領域,首要的重點不在「怎麼測」,而是在於了解圖形有什麼樣的「性質」。這裡頭不完全是隨機的東西,deterministic 的分析也是拉裡拉雜一大堆。說難其實不難,關鍵在於抓不抓的到 physical meaning 在哪裡。如果只有靠自己硬想,而不看看前人的著作,根本沒有辦法培養 sense,當然也更不知道這領域的題目該如何下手。老師覺得我之前花太多時間在 study,老實說我還沒有真正去 survey property testing 過。

突然真的覺得需要好好 survey,不然「一點 sense也沒有」的感覺好可怕。只在那邊空想,一點進展也沒有。「思而不學則殆」,大概就是這個意思吧。至於 survey 的工作,我想我要抽空來做。老實說,其實我認為自己並沒有遜到看不懂這領域的文章耶。我只是需要一點時間。現在不做這些事情,之後大概也沒什麼機會搞出什麼好成果吧。

Friday, June 20, 2008

A friend surprising me by Latex Beamer

今天我在 msn 上遇到老江,一個中山應數所的朋友。他的碩士論文題目是關於台灣馬拉松選手成績的預測,說來這題目跟他有很大的關聯性。我好奇向他要了口試投影片,一打開來發現居然是用 Latex Beamer 做的,令我大吃一驚。經我一問之下,才曉得原來是老闆的要求。當然,論文也必須用 Latex 來寫。他說,一開始完全不會,不過既然是規定,最後一定會上手。
這下我們資工系的學生汗顏了。在國際研討會上,大部分的投影片還是用 Powerpoint,我們台灣 theoretical computer science 的學生,幾乎都是屈服於微軟的淫威之下。有時候看到別人用 Beamer 做投影片,都會打從心底肅然起敬。老江說,我們這一行需要很多數學符號,難道不用 Latex?所以這才是我們汗顏的地方。

Powerpoint 的優點是上手容易,也容易使用動畫。但是因為相容性的關係,在正式場合出狀況的情形履見不鮮。另一方面,Beamer 雖然沒有那麼容易上手,不過做出來的投影片應該是每一台能夠看 pdf 檔的 PC 都能正常讀取與播放,出狀況的機率大概趨近於零。其實台灣的大專院校普遍被微軟攻佔,已經不是新鮮事,而且看起來政府也認為這是 e 世代的充分條件。這到底是好是壞呢?

Thursday, June 19, 2008

A similar webpage of mine

http://www.cmlab.csie.ntu.edu.tw/~sysrq/

這個人的 homepage 看起來跟我的「很像」,其實有百分之九十是一樣的吧。之前在木星站上面有提過這件事情還有這個網頁,我記得我也有跟當事人聯繫過,不過看起來是沒什麼用。感覺不是很舒服。

老婆聽我在抱怨,覺得我很煩。總之,就順其自然吧。如果變成台灣人網頁的範本,說不定也不錯,只要不會聽到人家說我是抄襲別人的網頁就好了。

OS: 蘇馬克看到那個網頁,問我說是不是抄他的。 XD

其實這件事情就算了,現在先把研究做好比較實際吧!

Wednesday, June 18, 2008

How Do I Look?


攝於 Galeria Kaufhof, Aachen (May 10, 2008)


奇怪了,明明看起來還不錯啊,挺有型的。感覺有點像魔鬼終結者,也有點像方大同。老婆卻說醜死了。

大魚說看起來老了 20 歲...

被唸藝術的朋友這樣形容,我要好好檢討。哈哈~

Indistinguishability of property testings

粗略地說,兩個 graph properties 若為 indistinguishable,則在某種程度上來講,它們是非常相似的性質 ("很難分的出來")。根據 Alon et al. 在 2000 年的一個 lemma:

If P and Q are indistinguishable graph properties, then P is testable if and only if Q is testable.

這個 lemma 的證明,大致上是利用 PQ 當中一個 property 的 tester,經過稍微修改之後,拿去測另一個性質。反正他們很「相似」,所以 testing 的效果不會差多少。

所以說,就像證明 NP-hardness 的 reduction 一樣,要證明 testability 也有所謂的 "reduction",靠的就是 indistinguishability 的推導。

Tuesday, June 17, 2008

Corresponding author 一問

經常聽人家講到 "corresponding author" 這個名詞,到底誰是 corresponding author,又誰該當 corresponding author 呢?

依照這裡的解釋,其實 corresponding author 就是指投稿過程中負責草稿的作者,工作包括 投稿、修改等事情。
...the Corresponding Author is the person who is responsible for the manuscript as it moves through the journal's submission process...
依照另一個網站上的說法:
...國科會生物處評比研究人員的貢獻時,將 First author 和 Corresponding author列為貢獻最高者,其餘的作者則按照合著人數多寡而定...
這樣子看起來,這地位好像蠻重要的。如果說從作者群裡面挑選一個比較有影響力的人當 corresponding author,說不定文章被接受的可能性比較大。不過 Peter 倒不這麼想,也就是說,關於接下來我們要投稿的文章,他希望由我一個人全權負責就是。

不過我希望 Peter 能再看一下準備要投出去的文章,這樣比較令人我安心一點。就先等他身體好一點吧。

Monday, June 16, 2008

Error probability of majority vote

假設我們有一個針對性質 P 的 tester,其成功機率至少為 2/3,那麼重複執行這個 tester 三次,以所謂的 "majority vote" 來當 output 的答案,那麼這樣子 testing 成功的機率至少有多少?

Paper* 上寫明為 20/27,但是我從 Chernoff bound 繞了一大圈,始終得不到這個答案。後來我才發現,是我殺雞了牛刀的關係。

從 tester 三次的 outputs 來看,taking majority vote 的失敗情形,只可能為 0 次 "yes" 與 1 次 "yes" 兩種。因此,



這樣子就說得過去了。能 "exactly" 分析當然比較好,Chernoff bound、 Chebyshev inequality 或 Markov inequality 只能說是「沒有辦法中的好辦法」。不過,花點時間練習使用 Chernoff bound 當然也是一件好事。久久沒做演練,數學技巧都有些生鏽了。


* 正在拜讀的 paper:
N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy: Efficient testing of large graphs. Combinatorica 20 (2000) 451-476.


Tuesday, June 03, 2008

LOVE to do or HAVE to do?

仔細觀察台灣的研究生和德國的研究生,總覺得前者少了一股熱忱。因為德國的升學制度的關係,真的要很想繼續唸上去才會升學,而且他們不念大學的出路也不差。台灣現在則是文憑至上,不唸都不行。所以,關於做學問這件事情,我們需要捫心自問,到底我們是 "LOVE" to do 呢,還是 "Have" to do?

當初決定唸博班,原因除了不習慣業界的生活以外,最主要是因為我喜歡學東西、想問題。對我來講,每天能看 papers、思索研究的問題,是很有趣的事情。每每看到大師的著作,都使我內心澎湃不已。雖然也不是沒有令我挫折的事情,但是大致上我很 enjoy 目前的生活。而且當初想都沒想到,我居然還可以來德國一年做研究,而且連老婆也帶來了。

中間這位.............是蕭博文嗎???

Sunday, June 01, 2008

Goodbye, my nerve

陪伴我二十幾年的神經


在 2008 June 13,經過一番的努力搶救,終究還是把神經抽除了。Josef 說是我台灣牙醫師的問題,讓後面兩顆牙蛀的不像話,所以建議我回台灣後乾脆換一個牙醫師。

Josef 說,今天來找他還真是來對了。他沒想到我的問題這麼嚴重,原本他不想抽除神經,希望先填塞藥物試試,不過在鑽牙的過程當中我哀嚎連連,不停祈求上帝救我。他發現情況遠比他想像的更糟,於是決定抽神經 (幾乎快死掉的一條)。我跟他要了神經的「屍體」,拿回家拍照紀念。

畢竟它也是想警告我細菌入侵而已。它沒有錯,錯的是細菌。

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 剛好就是我要報告的那一天,我想到時帥氣的短袖就可以派上用場了。

Sunday, April 20, 2008

Illness...That's too bad!

昨天晚上喉嚨開始痛了,上網查了查症狀還有拿鏡子自己檢查了一下,覺得應該是病毒引發喉嚨疼痛。處理的方法可以多用溫水加鹽巴漱口、多喝開水、吃普拿疼。現在還不到吃消炎藥(抗生素)的地步。唉,真是有夠衰的!因為身體不舒服,恍恍惚惚也不知道能做些什麼事。

老婆這禮拜幾乎都不在家,煮飯買菜要自己來。前幾天晚上因為嚴重的心律不整使我根本無法成眠,不知道是因為感冒病毒引發的症狀 (Josef 說的),還是因為我把菜炒的太鹹了 (Josef 說,過多鹽會讓腎臟工作量變大,引發血壓上升,所以心臟就會「很有感覺」)。感覺這幾天每件事都搞得一團糟 (ex: 禮拜二晚上炒飯加了尖頭高麗菜進去後,味道變得有點怪…) 在這個節骨眼真的是特別想念老婆,晚上一個人在家都空蕩蕩的,就算上批踢踢當鄉民也 high 不起來。

在 Kunkenhof Garden 手拖手

Sunday, April 13, 2008

Post of flags

大約三、四天前,不知道是誰在我們辦公室附近公佈欄前面貼了一張西藏的雪山獅子旗。我想歐洲人蠻挺西藏的吧!過了不久後,一張大大的中國五星旗也貼在旁邊。 Peter 覺得應該貼一張台灣 (中華民國) 的國旗,感覺也挺好玩的。結果陸陸續續一堆有的沒的都貼了上去,照片如下。



蘇馬克傳給我一個論壇網址,這個論壇上面有人 Po 文如下:
今天偶然间在Theoretische Informatik的Aushang里看到有人贴雪山狮子旗。于是我们再旁边贴了一张中国国旗(一样大的A3纸)予以回击,之所以没有把他们的旗子撕掉是因为德国不是提倡言论自由吗,还是给他们一个发言的机会。过了一会儿,雪山狮子旗的下面有贴出来一个台湾的青天白日旗。 他们所得人不许我们再贴中国国旗,说这里只能贴National Flags. 怒了!跟他们争辩两个都不是nations没用。再贴中国国旗也没用,在德国人 眼里都是平级的。我们于是又贴出来一张中国地图,上面当然包括西藏台湾还有“One China" 字样来回应。过了一会儿又有人贴了一张纸,上面是Dalai Lama的头像,还有一句话”In the practice of tolerance, one's enemy is the best teacher“,大家帮忙想想用什么来反击!注意,不要violent的话

我看了這個文章真的很不舒服!還好他們沒有真的把雪山獅子旗給撕掉。我只能說,在沒有言論自由以及充滿問題的教育環境中長大的人,思想偏差得很嚴重。請你們搞清楚,你們現在可是在一個有言論自由的國度裡,你管人家說什麼還是貼什麼,那都是人家的自由,你「回擊」個什麼鳥?我看你們不習慣自由也看不慣人家享有自由吧。

另一個回應:

最简单的就是:世界上只有一个中国,这是常识!


最近兩岸的共是不就是這樣嗎?先朝互不否定努力、互相尊重吧。

Thursday, April 03, 2008

Quotes about Ph.D training & problem solving

今天看到 PTT 上面一篇文章,提到在某次座談會當中,有人提問一個博士到底有什麼不同。有一個研究生的回答如下:

Know how to cope with a problem even when I know nothing about the problem.

這句話對我來講,還蠻受用的。我想,這方面的能力我還有待加強!

目前我知道要解一個問題,可以先從了解問題的性質和結構下手,並且看看相關的 papers。甚至,還可以寫程式幫助觀察。關於解題的策略,可以試試看數學歸納法一步一步去推導,這是很常見的方法。或者是把問題做適當簡化或予以變形,看看能否先解決這個簡化或變形的問題後,再回頭去處理原來的問題。有時候問題可以分成很多cases,為了解決這些 cases,需要再進一步考慮 sub-cases,這也是一個方法,尤其在圖論問題上,經常可以看到這個策略。

有時候,對於一個待解的問題,我嘗試著做一些猜想,列出一些 claims,然後設法證明這些 claims 是對的。目前我手邊的問題就是這樣做。還有,原本一個有 deterministic algorithms 的問題,也可以試圖使用 fixed-parameter algorithms,甚至 randomized algorithms 來解決,這些都是可以不錯的出路。

遇到瓶頸了,就做些有氧的運動,或者乾脆看一些不相關的東西,或許靈感就會來了。

Wednesday, April 02, 2008

Working on property testing

最近被老師點出一個問題。針對一個 property testing problem,我原本的作法是證明出 ɛ-far 的 instance 會有很高的機率,具有我們想要的性質。如此一來,我們的 sampling algorithm 就能夠成功。但事實上,我們必須證明以下這點:

我們的演算法針對每一個 ɛ-far instance,都必須 reject with high probability


針對這一點,我還在努力證明當中。目前我們仍舊無法得到一個有力的結論。而我原本的 idea,就算可以對一個不一樣的問題得到一個 sublinear time algorithm,但是就變得不那麼有趣了。

所以說,我這回真的弄迷糊了,還好老師把我給拉了回來。同時,老師送了我一句金玉良言:

You should keep on going further and further.


希望,我每天都能有新的進展!

Sunday, March 30, 2008

Beginning of daylight saving time

今天凌晨一點後,也就是 10.5 小時前,我們開始得把時鐘和手錶的撥快一小時。也就是說,原本的早上十點,會變成早上十一點。歐洲的日光節約時間 (daylight saving time; summer time) ,正式於今日開始實施。

今天的日出時間變成 7:15 AM,日落時間則為 8:05 PM。以後會慢慢變成六點多天亮,而接近晚上九點才天黑,這一點對於遊客來講當然是很棒的一件事。

在前一週一陣大風雪後,氣溫慢慢有穩定上升的跡象,之後兩三天預估大多在攝氏 6-15 度之間遊走,不過禮拜三以後,又會降至 4-8 度。不管怎樣, Aachen 的風大,有時候雖然溫度計顯示 10度,感覺上只有 5-6 度,跟風寒指數 (wind chill factor) 有關。

隨著到來的春天,老婆的朋友們也即將造訪我們。接著的五月份,將會是今年我最忙碌的一個月份之一。

  • May 4: 參加 Düsseldorf Marathon。
  • May 13-19: 因為要到 Victoria 參加 IWPEC 2008 研討會,以及機票的問題,我得在那兒和 Peter、老闆一起待上幾近一週的時間。
  • May 23-26: 計畫與老婆到 Nürnberg、 Prague 玩個幾天,放鬆一下心情。
看起來,今年五月份我有接近一半的時間都不在 Aachen了。關於研討會,目前註冊和機票已經搞定了,住宿的事宜還要再等等。報告要用的投影片,最遲再一、兩週就一定要動工了。

Tuesday, March 25, 2008

Heavy snow recently

這一週以來下了不少雪,氣溫都在零度上下徘徊。今早打開家裡的窗戶一看,就是一片雪白。通常我們家窗外,因為地勢的關係,是看不到這麼多雪的,所以我想今天的積雪一定很厚。

迷人的白雪

Thursday, March 13, 2008

Difficulties for a teacher

昨晚跟老婆分享了去年我當講師的心得。我覺得身為一個「老師」真的有許多難處,很難找到所謂的「最佳」處理方法。我認為以下的問題是必須要面對或是克服的:


  • 學生有意見卻不適時反映

學生明明有意見,不管是對教學內容還是評分的方式,一開始都選擇沉默。往往到了學期末,甚至等到成績出來了,才會在部落格或 BBS 上大肆撻伐老師的不是或是對助教的不滿。我想,在學期剛開始以及學期中之時,要詢問同學的意見。只能說盡量啦,學生不講也拿他們沒皮條。就我個人來講,有時候我常常話講到一半音量就變小,這個沒有當場向我反映卻事後怪罪於我,我就覺得很無辜。

Tuesday, March 11, 2008

The first 3 of 8 - about the qualification of Olympic baseball game

今年中華棒球隊參加奧運八搶三資格賽,前三名篤定可以取得北京奧運的入場卷。但是,這個賽制引發了一個數學問題:

究竟至少要贏幾場才能保證晉級(得到前三名)?

Thursday, March 06, 2008

Ice-cold shower on my legs

延伸閱讀: (出自孵蛋箱討論區)

雖然正值冬末春初,但這裡的冷水仍然接近零度,恰好可以搭配類似冰水澡的套餐。我的方法是,只著上衣,然後以蓮蓬頭出水沖雙腿。除了高強度練習結束後可以嘗試以外,如果旅行回來當天雙腿疲憊,一樣可以試試。但是過了 48 小時之後,應該要改成熱敷。

頻繁地替換跑鞋、確實做好暖身收操、多跑草地、高強度練習後喝巧克力牛奶與吃一點小點心,之後雙腿沖冰水,這些都是我最近一直進行的保養動作,而雙腿的狀況也正穩定中恢復當中。 只是沖冰水帶來的震撼,絕非罵出三字經可以舒緩的。雖然當下萬分煎熬,不過出了浴室之後,感覺雙腿的血液快速往上回流,漸漸地會感到十分舒暢。以目前三、四次的經驗看來,沖冰水真的是蠻有用的,雙腿的疲勞感很快就會消除。

Wednesday, March 05, 2008

No truth, except BLUE and GREEN

最近上奇摩新聞觀看政治 (或教育) 相關的新聞,我發現裡頭的心情投票有些「奇怪」。只要一則新聞稍微偏泛綠,絕大多數的人一定是投「無聊」。但是對泛藍稍微有利一點的新聞,大家都投「高興」一票。投票的人數並不少,先不論是不是所謂的「網路黨工」所為,我覺得這都隱約透露出一個值得注意的現象:

在目前的台灣社會,一件事情只要跟政治扯上一點點關係,已經沒有對錯可言,只有的分別。

真的是這樣子嗎?難道每一件與政治相關的事情完全沒有對錯可言?當然事實上絕非如此。這個情形就好像某某名人已經被鄉民冠上嘴砲王的稱號後,他講些什麼話完全不會被重視。

另外,我覺得愈來愈多人變得不夠溫柔、不能接受他人的想法。然後,只相信自己所願意相信的事實,慢慢缺乏對與錯的判斷能力了。難道,這就是真正的鄉民?

Tuesday, March 04, 2008

Heavy snow last night

沒想到, Aachen 最近下了兩次雪,這跟朋友們說的不一樣。
I'm sorry. Perhaps there is no snow. - by Josef and Dr. Krenz.
看來我們的運氣還真是不錯。

今天一大早起來,外面頓時變成白茫茫的世界。因為到處都是白白的,所以就算沒有出太陽,還是會覺得很亮!原本綠色的樹木和草皮,全部變成白的。大大小小的車子像是戴上了白色的帽子,像是有人惡作劇一樣,黏上了一堆棉花。大人們忙著鏟雪,小孩子則是高興地堆雪人。就連細細的欄杆上也有厚厚的一層雪,就像雪糕一樣,而且我還可以看到欄杆上排了五、六隻小雪人。草地上的雪人當然是更大隻。只是說,這些小孩子不怕沾到狗大便嗎?雖然德國的狗大便不像比利時那麼多,不過如果走在草地上,可是一不小心就會中獎的呢。

一旦下雪,地面就會變得很濕滑,沒有踩穩的話,很容易就會滑倒。如果是跑步的話,那就更刺激了。大夥兒開車一樣得小心翼翼地,尤其是轉彎的時候,速度一定得放慢才行。我盡量都走在厚雪處,比較不會滑。昨天晚上本來想騎腳踏車到辦公室來,不過昨晚下大雪,以及上次在雪地騎腳踏車的經驗後,我還是乖乖選擇搭公車出門,比較舒服又安全。

白色的 Aachen,別有一番風味呢。只是,還蠻冷的~


住處附近的公園

Monday, March 03, 2008

Delicious bendom

每次一到了午餐時間,總是令我格外期待,因為有老婆幫我弄的愛心便當。

其實便當裡面裝的倒也不是什麼驚奇的飯菜,都是簡單的家常料理,但是我覺得每一次就是很好吃。到了茶水間把便當微波之後,香味四溢,真的會引來旁人羨慕的眼神。

今天當我吃著美味的便當時,難得太陽漏了臉,金色的陽光射進辦公室裡,感覺人生真是充滿了希望。

我愛便當。


附上晚餐的麻婆豆腐:



[Forwarded] Storm is coming tonight!!

從鍾同學那兒轉來的訊息。
Mark Su 那邊也提供了相關新聞連結

話說 Aachen 這裡經常刮起狂風,威力可不輸給台灣的颱風喔。


---------- Forwarded message ----------
[Details of email address are omitted]

Hello everyone,

The storm is coming tonight! so please take care
yourself.

Might be very dangeous!!!! so it's better to stay at
home.

http://www.wetter.com/v2/index.php?SID=&LANG=DE&LOC=1101&id=7121

chenghan



-----------------------------------
Cheng-Han Chung
Institut fuer Theoretische Physik E
RWTH Aachen
[other information is omitted]
-----------------------------------

Friday, February 29, 2008

Working on the final version of the paper

投上了 IWPEC 2008 以後,收到了 referees 的 comments。覺得不能置之不理,於是我花了一點時間根據這些 comments 來修飾 paper。我依照 Peter 的建議,先從 full paper 寫起,把文章潤飾的更好後,最後才來縮減篇幅。不過這個流程跟老師的建議恰好顛倒,所以老師便覺得我的手腳太慢。

跟 Peter 前前後後改了好幾個版本後,終於我們要認真考慮投稿至 IWPEC 的 final version 了。頁數限制跟先前的初稿一樣,也是十二頁,並沒有比較多,而且這一次不允許 appendix,所以我們不能把東西全丟進後面的 appendix。那證明怎麼辦?小定理和引理的證明全拿掉了,而 paper 裡有三個演算法, Peter 不想拿掉任何一個,所以只好以精簡的敘述呈現。至於最麻煩的第三個演算法,原本時間複雜度的章節全部拿掉才能勉強擠進 12 頁,好不容易在把整篇 paper 小幅改寫之後,多出了將近半頁的空間可以應用,終於可以對於第三個演算法的時間複雜度稍做著墨。

等老師看了之後,剩下的工作就是把 paper 上傳至 EasyChair Conference System,以及傳真 copyright 出去。不過要注意 paper 的 submission deadline 是以 GMT 時間為準,所以就是我這邊的三月三日 22:59:59。

其他像是加拿大簽證和訂機票的事情,我還得詢問一下 Birgit。

Monday, February 25, 2008

So Not Over You

So Not Over You
Simply Red 2008 年的最新單曲,收錄在 專輯「Stay」。

這首歌絕對是經典,歌詞也十分感人。主旋律與歌詞雖帶著悲傷,但副歌卻隱約述說昔日愛情的甜美,最後則試圖說服自己美好的時光已逝。再搭配 MV 的畫面,只能用"完美"兩個來形容。

主唱 Mick Hucknall 表示,Stay 將會是 Simply Red 的最後一張專輯,等 2009 年巡迴演唱會結束後, Simply Red 將解散 (split)。他表示,對一個團體而言, 25 年的歲月夠長了。而且他希望能找出不一樣的音樂元素,所以必須擺脫 Simply Red 的桎梏。

自己試著翻譯的中文歌詞:

不知道為什麼 我還是睡在床上 過去屬於我的這一側
自從你離開之後 空虛感一直在我腦海中反覆浮現
我告訴自己 日子還是得過下去
別再後悔那些 我沒講出口的話了

所以我撕了妳的信 把妳的相片從牆上拿下來
我刪除了妳的手機號碼 因為我很難不撥這個號碼
覺得好過了些之後,我告訴我自己 一切都會沒事
我要為以後的美好時光而活

*無論我走到哪裡
總是能聽到一首 讓我想起妳的情歌
而即使我知道 我必須堅強起來
我還是無法對妳忘懷
因為我仍相信 而我也知道
這世界除了我們兩個以外 就什麼都沒有了

那美好的時光已逝
而我卻仍然無法忘記妳

所有的朋友都勸我 最好趕快找下一個對象
為什麼要在一無所有之時 把時間浪費在孤獨裡頭呢
我是個傻瓜
我以為我能夠忘記
但是我不能

*無論我走到哪裡
總是能聽到一首 讓我想起妳的情歌
而即使我知道 我必須堅強起來
我還是無法對妳忘懷
因為我仍相信 而我也知道
這世界除了我們兩個以外 就什麼都沒有了

現在 我找到了一個方法 把妳留在身邊
我把妳放在一個 我可以愛妳的地方
我只能祈求 把妳留在那兒 引導著我
我再也不需要 隱藏我內心的苦楚了

就是無法忘懷
儘管時光已逝
我就是沒辦法對妳忘懷

延伸閱讀:






原文歌詞:

Don't know why I still slept on my side of the bed
The emptiness when you were gone kept ringing in my head
Told myself I really had to move along now
Stop regretting all the things I left unsaid, yeah yeah

So I tore up your letters
Took your picture off my wall
I deleted your number, it was too hard not to call
Felt a little better, told myself I'd be fine
Got to live for the good times up ahead, yeah yeah

[chorus]
'Cos everywhere I go
There's a love song that reminds me of you
And even though I knew I had to be strong
I was still not over you
'Cos I still believe and I could see how there's nothing left of you and me
That time is over
'Cos I'm so not over you

All my friends try to tell me better find somebody new
Why waste time being lonely when there's nothing left to lose'
Anything to get you out of my mind
I'm a fool if I thought I could forget
And I could not forget

[chorus]
'Cos everywhere I go
There's a love song that reminds me of you
And even though I knew I had to be strong
I was still not over you
'Cos I still believe and I could see how there's nothing left of you and me
That time is over
'Cos I'm so not over you

Now I found a way to keep you there beside me
To where my love won't be denied
I can only hope to keep you there and guide me
There's no more need to hide from all this pain inside
Chorus

So not over you
That time is over
'Cos I'm so not over you

Monday, February 18, 2008

Some more work to do for the conference

Finally the list of accepted papers came out:


Paper 被接受之後,接下來有很多事情要忙了。

  1. 修改 paper,三月三日前截稿。
    • 有 referee 說,文章的篇幅都在許多不重要的地方著墨太多,應該要修改。而且演算法的正確性最好給一個證明,尤其是 quartet topology 重複修改的問題,這個地方要特別講清楚。
    • 先寫一份完整的 technical report 格式,再縮篇幅。
  2. 機票、註冊費與住宿。
  3. 申請加拿大簽證。
    • 看旅行社怎麼說,不過也是要一筆錢,估計在五千元左右。
  4. 經費補助的問題。
    • 問老師國科會那邊的錢能否給予我補助。
      • 已詢問。
    • 國內研究生出席國際學術會議的申請額度至多三萬元。
      • 需要知道研討會註冊費,已經寫信詢問 chairs。
    • 已寫信至國合處陳先生那邊詢問從德國參加加拿大會議的請款問題。
    • 已寫信至駐得科技組黃博士那邊詢問補助的辦法。
      • 只補助參加歐陸地區的研討會。

Mark 說,以後乾脆小孩都到美國生好了,這樣到很多國家都不用煩惱簽證的問題。但是,萬一以後我們家有人要選總統該怎麼辦啊?(Mark 說:「那就去選美國總統啊!」)

Friday, February 15, 2008

Notification of the paper

Dear Maw-Shang Chang, Chuang-Chieh Lin and Peter Rossmanith,

On behalf of the IWPEC 2008 program committee, it is our pleasure to inform you that your submission

New fixed-parameter algorithms for the minimum quartet inconsistency problem

was accepted to IWPEC 2008. Congratulations!

The selection of the papers was a challenging and difficult task. The Program Committee members have put in a substantial effort in order to provide useful feedback to authors. We will forward the comments on your paper within the next few days.

We expect that each accepted paper will be presented by one of the authors at the conference.

In a few days you will receive instructions for producing and sending the final conference version. In order to be included in the proceedings, the final version of your paper must be received no later than Sunday, 3 Mar 2008.

Thank you very much for contributing to IWPEC 2008. The program committee and we look forward to seeing you at the conference.

Sincerely,

Martin Grohe
Rolf Niedermeier
(Program Co-Chairs, IWPEC 2008)

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

噫,好。我中了。

Saturday, February 02, 2008

[轉錄] 許台灣一個未來:打造實力國家 (李家同)

許台灣一個未來:打造實力國家
【聯合報╱李家同/暨南大學資工系教授(投縣埔里)】

http://udn.com/NEWS/OPINION/X1/4206629.shtml

Thursday, January 31, 2008

Some useful mathematical formulae



  • 1/(1+x) = 1 + O(x) when x is small.

  • , where .

  • If and , then .
  • , where