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

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