Thursday, January 31, 2008

Some useful mathematical formulae



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

  • , where .

  • If and , then .
  • , where


Tuesday, January 29, 2008

Interesting papers

  • Justin G. Chen, Scott D. Kominers, Robert W. Sinnott: Walk versus Wait: The Lazy Mathematician Wins: arXiv.org,
    • 懶是上策?!
  • Artur Czumaj and Christian Sohler: (Draft) A survey on sublinear time algorithms.
    • 另一篇關於 subliear time algorithms 的 survey
  • Ziv Bar-Yossef, Ravi Kumar: Sampling Algorithms: Lower Bounds and Applications. STOC'01
    • 看看這篇說不定能幫助我更加深入了解 sampling algorithms
  • Rajeev Motwani, Rina Panigrahy, Ying Xu: Estimating Sum by Weighted Sampling. ICALP'07
    • 喔?!這一篇算是蠻新的吧!
關於第一篇的線上comments: http://tinyurl.com/2vudqd

第一篇 paper 主要是證明了如果步行前往目的地仍可及時到達,那麼只要決定以步行前進,中間遇到每個公車站牌最好都不要停下來,也就是說,一決定撩下去就不要三心兩意,直接一路走到底就是。 paper 裡面的最終結論之前,推論最好先原地等待公車,直到用走的都無法準時到達之前才放棄等待。

所以說標題下的結論,其實是指一開始先在第一個站牌原地等公車,因為走到前面幾站等並不會比較快到目的地。而且並不是要傻傻的等,如果用走的都快來不及了,就得認命趕快用走的。

關於第二篇, BarrosH 說他看過,所以我們經過一點討論之後,使我對於一開始的 "Basic Sublinear Algorithm for searching in a sorted list" 更加了解了。原來他的 doubly linked list 還多了一個輔助的 array 當 index 啊。

關於第三篇,不愧是 STOC 出品,還蠻難的。不過看得出作者已經寫的很仔細了。一開頭有介紹 randomized decision trees,跟傳統的 deterministic decision trees 很像,只是同一個 input 可能有很多條從 root 到 leaves 的可能路徑,每個 internal node 包含了 query 以及擲骰子的可能性。裡面重要的名詞,包括 disjoint inputs,各式各樣的 approximation concepts, Block Sensitivity 的概念。光是搞懂這些基本定義,就得花上不少時間。


Best wishes for the paper

Peter 不放心我們的 paper 會不會被接受,所以說想去教堂點一盞燈,祈禱 referees 會接受這篇 paper。我想我也會在每次用餐時祈禱。這麼說來,老師不就可以去孔廟找孔子聊聊了?

這篇的結果跟其他的結果在伯仲之間,但希望評審委員能接受了!

Monday, January 28, 2008

Recent calls for papers



Friday, January 25, 2008

The 3n+1 conjecture (Collatz's conjecture)

The 3n+1 conjecture (Collatz's conjecture), forwarded from Open Problem Garden.

Let f(n) = 3n+1 if n is odd and n/2 if n is even. Let f(1) = 1. Assume we start with some number n and repeatedly take the f of the current number. Prove that no matter what the initial number is we eventually reach 1.

It can be also obtained from Wikipedia. This problem is worth at least $500 US dollars. Refer to this page for some results of computational verification. I also wrote a very simple program to verify this conjecture.

This is an an open problem for the moment, and it seems to be given on an graduate school entrance exam. To find a function g (n) such that f(n) = O(g(n)) is then an open problem, too.

It's very interesting. By the way, I found "Jones' conjecture", posted by Chuan-Min Lee. I hope that someday I will post an interesting and important open problem or a conjecture, too.

Wednesday, January 23, 2008

A picture taken when Peter visited CCU, Taiwan

Professor Peter Rossmanith 於 2007 年造訪中正大學資訊工程學系計算理論實驗室兩次, Post 上這張照片當作紀念。


Tuesday, January 22, 2008

桑田佳祐 - 明日晴れるかな

桑田佳祐 - 明日晴れるかな



我和老婆都很喜歡的歌。可以說是經典了!

Joseph, Chuang-Chieh Lin's Homepage

Since my homepage cannot be visited by Google robots, I post it here.


It has been updated for several times.

Monday, January 21, 2008

Terence Tao's homepage and blog

一個強者 - 陶哲瑄的個人網頁與部落格:
http://www.math.ucla.edu/~tao/
http://terrytao.wordpress.com/

供觀摩和景仰用。

看起來他也有在做 property testing!我的天啊...

Chinese Translation of my personal homepage

底下連結是經由 Yahoo 翻譯我的個人網頁而得到的結果:
http://tinyurl.com/36twpk 中文版
http://tinyurl.com/3y3gsw 德文版

看起來挺妙的!錯誤也沒有想像中那麼多。

Room405, 計算理論實驗室,
電腦科學系和資訊工程學
全國鍾・城大學, 分鐘Hsiung, Chia-Yi, 臺灣, 621
電話: 886-5-2720411-23135; 886-49-8021028
電子郵件: lincc_AT_cs_ccu_edu_tw; josephcclin _ AT_gmail_com

我是Ph.D 候選人臨時地。
現在我做□研究在電腦科學系,
RWTH 亞琛大學, 德國
由於DAAD-NSC 三明治Programm 。

我親愛的顧問 :
Maw-Shang Shang Chang (禮物) 教授 ,
R. C. T. 李教授(前)
...
...
不過「亞琛」應該翻成「阿亨」比較好!

認為艱苦, 和艱苦然後工作。

這個太妙了。

Sunday, January 20, 2008

My poor teeth...

There are always troubles with my teeth. I just lost half part of one tooth by accident. I think I'd better go to Josef Kunze's clinic as soon as possible, if I don't want to lose the rest part of it.

So terrible for me. Oops!

W3C HTML 4.01 Transitional validation passed!

Finally I made my personal homepage pass the validation!! It is not so easy for me to refine the homepage from the original Microsoft Frontpage webpage to a valid W3C html one.

Congratulations

The document located at http://www.cs.ccu.edu.tw/~lincc/ was checked and found to be valid HTML 4.01 Transitional. This means that the resource in question identified itself as "HTML 4.01 Transitional" and that we successfully performed a formal validation using an SGML or XML Parser (depending on the markup language used).
And I got this:

Valid HTML 4.01 Transitional


The following paragraph is an interesting FAQ:

Is validation some kind of quality control? Does "valid" mean "quality approved by W3C"?

Validity is one of the quality criteria for a Web page, but there are many others. In other words, a valid Web page is not necessarily a good web page, but an invalid Web page has little chance of being a good web page.......


To validate your website, try W3C HTML Validator: http://validator.w3.org/

Friday, January 18, 2008

Thanks to my dear wife

我常在想,如果當初老婆沒有跟我一起來德國,我現在會變成怎樣?我想,除了孤獨之外,生活起居都會成為問題。少了她,去哪裡都沒有方向感的我一定老是迷路。少了她,我三餐一定隨便吃吃,身體健康一定垮。少了她,忘東忘西的我必定老是浪費時間在重複做同一件事情上。如果沒有她,我的穿著和言行不得體的情況一定會屢見不鮮。

現在每天最期待的事情,就是吃他為我採買的早餐,以及一起準備與享用晚餐的時刻。因為我常常幫倒忙,所以多半退居二線勤務 - 洗碗盤、擦碗盤、倒垃圾等等。這樣的生活雖然簡單,卻令我著實感到幸福。

我常常做一些蠢事,或是做一些無理的要求,發些莫名其妙的脾氣,但是老婆總是容忍我。有時候想想,我還真的蠻幸運的。我娶到了一個可愛又漂亮(她說沒有漂亮),而又總是給予我許多的協助和包容的好老婆。

這些日子以來,真是辛苦她了!我真的也很感謝她所做的一切。希望我們能攜手繼續過著這樣幸福簡單的日子,直到永遠。

Tuesday, January 15, 2008

葛若琳 (Caroline Gluck) BBC 特約記者

聯合新聞網上的報導。
http://udn.com/NEWS/NATIONAL/NAT5/4181243.shtml
聯合新聞網上的報導。
http://udn.com/NEWS/NATIONAL/NAT5/4181243.shtml

Caroline Gluck 的部落格: (caro's choice)
http://caroschoice.blogspot.com/

從英國人的角度來看台灣,還蠻有趣的。她的 blog 裡面提到台灣缺少英文的資訊,讓外國人想在台灣旅遊十分困難。

政府嘛幫幫忙,難怪旅遊搞不起來。

Monday, January 14, 2008

My Cherie Amour (by Stevie Wonder)

La la la la la la
La la la la la la

My Cherie Amour, lovely as a summer's day
My Cherie Amour, distant as the Milky Way
My Cherie Amour, pretty little one that I adore
You're the only girl my heart beats for
How I wish that you were mine

In a cafe or sometimes on a crowded street
I've been near you, but you have never noticed me
My Cherie Amour, won't you tell me how could you ignore
That behind that little smile I wore
How I wish that you were mine

Maybe someday you'll see my face among the crowd
Maybe someday I'll share your little distant cloud
Oh, Cherie Amour, pretty little one that I adore
You're the only girl my heart beats for
How I wish that you were mine

La la la la la la
La la la la la la

Sunday, January 13, 2008

Runners Point and Dom neighborhood

今天早上與 Dr. Josef Kunze 有約,搭他們家的 family car 前往市區逛逛。一開始我們先到一家模型店,Josef 和他的大兒子想要修理他們的火車模型。那間店就在 Dom 附近,距離 Kaiser 只有不到 20m 遠。不管是火車、鐵軌、隧道、樹木、花草、各式各樣的人物模型、飛機、汽車、摩托車等等,都是應有盡有,而且維妙維肖,十分地精細。

逛完了模型店,他帶我到 DomCity Hall 附近,向我解說哪些部分是年代較久遠的的建築。還特別指明廣場上一塊地板底下,埋了很多死人頭。此外,經過他提醒後我才發現,原來我還沒有參觀過 Dom 旁邊的寶藏室。他建議我一定要進去看看。進入了 Dom 之後,他問我有沒有發現吊起燈臺的繩索不太一樣,原來這條由一串鐵環所連結而成的繩索,每一個鐵環都比下面的鐵環來的大,所以由下往上看就不會感覺繩索變得愈來愈細。沒有他的解說,我一定不會發現這一點。

出了 Dom 之後,他還向我介紹了傳說中撒旦要求當地居民建造的房屋。據說撒旦要求居民造完了屋子,還得獻上一個人的靈魂。沒想到居民居然放了一隻狼還有它的靈魂。狼和靈魂 (像一顆超大的松果) 都可以在 Dom 的入口看到。還蠻妙的。

接下來就是今天的重頭戲,要去 Runners Point 量測我的跑姿與腳底板的大小數據。經過攝影觀察,老闆認為我有外翻的問題 (找時間看一下這兩篇 [1], [2]),所以需要改善外翻的鞋子。因為 Josef 跟老闆熟識,在挑選了幾雙適合的鞋子試試之後,Josef 幫我要到了一個不錯的價錢,一雙 NIKE 慢跑鞋可以賣我原價五折,大約要價台幣 2300 元,算是非常便宜!而且買完鞋以後,還可以免費報名參加六月的 Aachen 半馬賽,等於省了 65 歐元以上。不過,還是得等下一期的生活費下來再說。只能叫老闆先幫我保留我的各項測試數據了。

Josef 的建議與 wes 的很類似,他說寒冷的冬天應以建立里程為主,速度練習可以先擱著。令我訝異的是,一天 30 km 的里程對他而言幾乎是隨手拈來。希望三月底之前,他能確定跟我一起參加 Düsseldorf Marathon。前提是,他得過老婆那一關才行。

此外,Josef 以嚴肅的口吻警告我必須再去一次他的診所看診,否則,我很可能將失去我可愛又珍貴的牙齒。大概一個禮拜之後,我得去一趟他的診所。他說:"After you are tortured by me, we can do a long run." 其實,我不怕看牙醫,我只是怕「太常」看牙醫而已。

今天下午,我以緩慢的配速完成了 25 km 的小長跑 (費時約 2:02:00)。我想,對身體的負擔應該是夠小了。

Wednesday, January 09, 2008

Updating the personal homepage

還記得許久之前,我的一位大學同窗笑我,怎麼會敢把自己上過的課程放在個人網頁上 (而且修課成績大部分都很糟)。如今,總算是把這個項目,以及其他雜七雜八的東西全部都拿掉了。加上了 Curriculum VitaeMy Blog 到我的 index 裡面。整個網頁看起來變得比較簡單一點,而且個人圖片的位置也不會因為瀏覽器的關係而到處亂跑。

此外,我的 Journals and literatures 也改成 Journals, Conferences, and Literatures,並且大幅增加重要的 conferences 名稱與連結。我知道有人把這些 conferences 分成三個 ranks,不過我覺得這個跟個人喜好和主觀因素有關係,所以我不做明顯的排名,只是依照我所認為的重要性以先後順序排列。

近期的 Call for Papers 連結:
掌握這些資訊蠻重要的!

Tuesday, January 08, 2008

Glucosamine & chondroitin

感謝老婆的支持和大魚的熱心建議,我總算在 Apotheke am Steppenberg 買了一罐葡萄糖胺 (Glucosamine) 與軟骨素 (chondroitin) 的混合錠,價格是 27.4 歐元,應該是不算太貴。估計是一天飯後服用兩顆,估計可以吃 45 天份。希望對我的膝蓋關節炎有所幫助。

參考資訊如底下網頁:
http://www.wedar.com/health/show.asp?id=1721

節錄自該網頁:

通常老年人 (嗚~) 容易有的退化性症狀, 以關節炎和記憶力退化最令人困擾。 退化性關節炎的發生是由於軟骨遭破壞所致,現代人缺乏運動,易造成關節老化,而骨刺及膝關節退化都與之有關。葡萄糖胺 (Glucosamine) 易為人體 所吸收,可促進關節軟骨素 (chondroitin) 及關節液成分 Hyaluonic acid 之形成,增加骨關節的黏稠彈性,改善關節退化、摩擦發炎、疼痛、腫脹變形,更可幫助關節代謝正常化,改善關節炎患者的關節活動功能 , 並增加骨質緻密度與堅硬度。另膠原蛋白為軟骨、肌腱、韌帶修復的主要成分。關節之間的軟骨就是膠原形成的,是連接組織的重要物質。退化性關節炎的發生是由於軟骨遭破壞所致,適量的補充膠原蛋白有助於預防及改善退化性關節炎。


Apotheke am Steppenberg:

Address: Steppenbergallee 12, 52074 Aachen
Telephone: 0241-873335


Study progress - [JKL01-SICOMP]

為了加強對於 quartet consistency 的背景知識,我正研讀 Tao Jiang et al. 的 paper:

T. Jiang, P. Kearney, and M. Li: A polynomial time approximation scheme for inferring evolutionary trees from quartet topologies and its application. SIAM J. Comput. 30 (2001) 1942--1961. [link]

這篇 paper 主要是介紹 MQC (maximum quartet consistency) 問題的一個 PTAS,以及重要的技巧: quartet cleaning。目前為止,我覺得這篇 paper 蠻容易懂的,希望不是假象。

至於之前研讀的 "The complexity of reconstructing trees from qualitative characters and subtrees" by M. Steel,符號和文句都不容易理解,但其實它最主要的貢獻也只在證明 (incomplete) MQC (MQI; minimum quartet inconsistency) 問題為 NPC,所以我想大概看看就可以了。

在讀了 related work 之後,我才驚覺我可能搞錯了某些觀念。當 input Q 不一定為 complete 時, M. Steel 證明了 MQC 為 NPC,於是可以得到 MQI 也為 NPC。但是當 input 為 complete 時,MQC 和 MQI 問題亦為 NPC,這個結果是由 V. Berry, T. Jiang, P. Kearney, M. Li 與 T. Wareham 在 ESA'99 (proceedings of the 7th Annual European Symposium on Algorithms) 共同發表的文章中提到的,因此並不是 M. Steel 證明的。

Friday, January 04, 2008

Home - Simply Red

每次聽到這首歌都會很想回台灣。歌裡頭的節奏就像搭乘火車回家一樣,不過從德國是不可能坐火車回台灣的。

What's worth nothing else but love
Take a walk down any street now
Every one of us in our own little world
Looking for a heart with whom to beat now

What's worth nothing else but love
I'm prepared to take the heat now
What's worth more than anything else at all
To keep you firmly on your feet now

So fake cool image should be over
'Cause I long for a feeling of home
Real life, depicted in song
A loving memory
After long, home is a place where I yearn to belong

Where the land meets the sea
She'll be smiling so sweetly now
I hope that she'll be here much longer than I will
My heart loves her with every beat now

So fake cool image should be over
'Cause I long for a feeling of home
Real life, depicted in song
A loving memory
After long, home is a place where I yearn to belong


Thursday, January 03, 2008

Paper submitted!! (IWPEC 2008)

這一次投稿的 paper,用到了一些簡單的圖論證明、 search tree 的結構、 求遞迴式與逼近特徵根的技巧 (所以也用到了一點微積分)、寫了三個程式找一些 branching numbers 等等,甚至還得自己證明出一些結果來幫助定理的證明。經過兩個月以來的努力,終於把 paper 投出去了! 希望我的第一篇 international conference paper 能夠順利出爐。新年第一 post,就是 paper submitted,希望今年能有個好采頭。