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


老實講,這個問題困擾我很久了。到底是我考慮的不夠周全(就是我太笨),還是他們寫不清楚呢?

之前老闆覺得我一直只在做 survey 的功夫,沒有把精力花在解決問題上。可是現在宣稱在做 property testing 的我,其實對這領域還是一知半解,相關的 papers 也沒認真看過幾篇。

目前我開始在看相關的 papers 了,過去的 conference papers 現在一篇一篇刊載上了 SIAM Journal on Computing,「好像」有比 FOCS 或 STOC 的版本好懂一點點。感覺上,他們還是著眼在「大問題」上,所以說我們還是有機會在小問題上努力。譬如,已知任一個 monotone graph property (closed under removal of edges and vertices) 為 testable ,但是 query complexity 可能是 exponential of (1/ϵ),如果可以降低這個 exponent,甚至降為 polynomial of (1/ϵ),我覺得都是可以做的。當然除了 graph properties 之外,還有很多 combinatorial properties 可以探討。所以,我想這領域還是很新很新吧。

現在比較頭痛的東西,除了 monotone graph property 定義搞不清楚以外,就是要把 Szemeredi's regularity lemma 搞清楚。粗略來說,這個 lemma 是告訴我們任何 graph 都能以 random graphs 來逼近。對我來講,想通如何應用它的方法是最重要的一件事。目前看起來,想要在這塊領域上有所成果,不把這個 lemma 搞清楚似乎是不行的。

3 comments:

BarrosH said...

科科,該說巧嗎?

之前我也跟我老闆說過 Monotone Graph Testing 應該是可以做的方向....XD

不過後來沒去做就是了.

Joseph, Chuang-Chieh Lin said...

到現在都還沒有回我耶...我又寫了信去問 Noga Alon 了。


我還真是大膽啊...

Joseph, Chuang-Chieh Lin said...

Professor Alon 的回覆:

Dear Joseph,

monotone decreasing or monotone increasing is essentially identical, as if P is a family of graphs which is testable, then the family of all complements of the members of P is testable as well, hence considering properties closed with respect to adding edges is the same as considering ones closed under deleting edges.

Best,
Noga Alon.