## Monday, December 29, 2008

### Mark & Eva's wedding party

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 (晚安)

### Exercises for randomized algorithms

• 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.

(左起: 顯如，阿哲，武雄學長，怡均，我，

## Monday, December 08, 2008

### I'm 29 years old now

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

「什麼？你結婚了？！」
「什麼？你已經博五了？！」

## 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

## Sunday, October 12, 2008

### A bash file for backup

#!/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"

## 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-guimakesu (if you're not already root)make install`

MPlayer 播放結果

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

「棒球不是台灣的國球」

## Tuesday, August 12, 2008

### People in Germany

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

### Too high sometimes

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

## Sunday, August 10, 2008

### Go Go Taiwan!!

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

## Wednesday, August 06, 2008

### Hereditary and semihereditary graph properties

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.

## Sunday, August 03, 2008

### Testing colorability & hereditary graph properties

• 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 應該是不錯的貢獻，可是作者的功力可得要有相當的程度才行。

﻿
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

• 考慮太多，優柔寡斷
• 完美主義
• 害怕失敗
• 挑簡單、喜歡的先做

## Friday, July 11, 2008

### Approximating the graph by empty graphs

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.

$\lim\limits_{n\to\infty}\frac{o(n^2)}{(\frac{n}{k})^2} = 0.$

## Monday, July 07, 2008

### Density of a regular pair is the average density of sub-pairs

$\{A_j\mid 1\leq j\leq l\}, \{B_j'\mid 1\leq j'\leq l\}$

$|A_1|=|A_2|=\ldots=|A_l|, \; |B_1|=|B_2|=\ldots=|B_l|$

$\sum\limits_{1\leq j,j'\leq l}d(A_j,B_{j'}) = \frac{\sum\limits_{1\leq j,j'\leq l}e(A_j,B_{j'})}{|A_1|\cdot |B_1|}$ .................... (*)

$d(A,B)=\frac{e(A,B)}{|A|\cdot |B|} = \frac{\sum\limits_{1\leq j,j'\leq l}e(A_j,B_{j'})}{|A|\cdot |B|}\\ = (*)\cdot\frac{|A_1|\cdot |B_1|}{|A|\cdot|B|}\\ =
\frac{\sum\limits_{1\leq j,j'\leq l}d(A_j,B_{j'})}{l^2}$

Theorem: Given a bipartite graph with classes A and B, then for all integers k < |A| and l < |B|, we have

$d(A,B) = \frac{\sum\limits_{X\subset A, Y\subset B,\\ |X| = k, |Y|=l} \quad d(X,Y)}{{|A|\choose k}{|B|\choose l}}$

## Thursday, July 03, 2008

### 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 $d> \epsilon > 0$, 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 $\epsilon\leq (d-\epsilon)^{\Delta}/(2+\Delta)$, then $R\subset G$. In fact, the number of labelled copies of R in G is at least $(\epsilon m)^{r}$.

(*) 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.

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 $Y\subset B, \; |Y| > \epsilon |B|$, we have

$|\{x\in A\:\mid\: \mbox{deg}(x,Y)\leq (d-\epsilon)|Y|\}|\leq \epsilon|A|.$

Proof:

Let $1 > \delta > \epsilon$ be a constant. Let
$X = \{\x\in A : \mbox{deg}(x,Y)\leq (d-\epsilon) |Y|}$

and assume that

$|X| = \delta |A|$. ..................... (*)

Hence we have
$d(X,Y)\leq\frac{\delta|A|\cdot (d-\epsilon)|Y|}{\delta|A|\cdot |Y|}\leq d-\epsilon$......................(1)

But $|X| > \epsilon |A|, |Y| > \epsilon |B|$, since (A,B) are ɛ-regular, we have
$d-\epsilon < d(X,Y) < d+\epsilon$..........................(2)

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

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

$C^{\log(1/d)^{k-1}} \leq N(k,d) \leq 2^{2^{d^{-2^{2^{k+9}}}}}$

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

## Wednesday, June 25, 2008

### Strange reasons (似是而非的詭論)

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

## Friday, June 20, 2008

### A friend surprising me by Latex Beamer

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

## Thursday, June 19, 2008

### A similar webpage of mine

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

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

## Wednesday, June 18, 2008

### Indistinguishability of property testings

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

## Tuesday, June 17, 2008

### 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列為貢獻最高者，其餘的作者則按照合著人數多寡而定...

## Monday, June 16, 2008

### Error probability of majority vote

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

${3\choose 0}(2/3)^0(1/3)^3 + {3\choose 1}(2/3)^1(1/3)^2 = \frac{7}{27}.$

* 正在拜讀的 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?

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

## Sunday, June 01, 2008

### Goodbye, my nerve

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

## Friday, May 30, 2008

### Concerning monotone graph properties

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.

Best regards,
Joseph

## Wednesday, May 21, 2008

May 18, 2008:

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

May 17, 2008:

 Peter 的姿勢與我的影子

May 16, 2008:

May 15, 2008:

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

May 14, 2008:

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

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

International Workshop on Exact and Parameterized Computation
Time: May 14-16, 2008

Before the conference

## Thursday, April 03, 2008

### Quotes about Ph.D training & problem solving

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

## Wednesday, April 02, 2008

### Working on property testing

You should keep on going further and further.

## Sunday, March 30, 2008

### Beginning of daylight saving time

• May 4: 參加 Düsseldorf Marathon。
• May 13-19: 因為要到 Victoria 參加 IWPEC 2008 研討會，以及機票的問題，我得在那兒和 Peter、老闆一起待上幾近一週的時間。
• May 23-26: 計畫與老婆到 Nürnberg、 Prague 玩個幾天，放鬆一下心情。

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

## Tuesday, March 04, 2008

### Heavy snow last night

I'm sorry. Perhaps there is no snow. - by Josef and Dr. Krenz.

## Monday, March 03, 2008

### [Forwarded] Storm is coming tonight!!

Mark Su 那邊也提供了相關新聞連結

---------- 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]
-----------------------------------

## Monday, February 25, 2008

### So Not Over You

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

*無論我走到哪裡

*無論我走到哪裡

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

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

• $e^a \geq 1+a$

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

• ${n\choose an} = O((\frac{1}{a^a (1-a)^{(1-a)}})^n)$, where $a\in (0,1)$.

• If $T(1) = 1$ and $T(n) = 2^nT(n/2)$, then $T(n) = 4^n$.
• ${n\choose k}\leq 2^{n\cdot H(k/n)}$, where $H(p) = -p\log p - (1-p)\log (1-p).$
• $\left(\frac{n}{k}\right)^k\leq {{n\choose k}}\leq\frac{n^k}{k!}\leq\left(\frac{n\cdot e}{k}\right)^k.$