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.
(舊文)

別老是搞不清楚了。