Wednesday, April 02, 2008

Working on property testing

最近被老師點出一個問題。針對一個 property testing problem,我原本的作法是證明出 ɛ-far 的 instance 會有很高的機率,具有我們想要的性質。如此一來,我們的 sampling algorithm 就能夠成功。但事實上,我們必須證明以下這點:

我們的演算法針對每一個 ɛ-far instance,都必須 reject with high probability


針對這一點,我還在努力證明當中。目前我們仍舊無法得到一個有力的結論。而我原本的 idea,就算可以對一個不一樣的問題得到一個 sublinear time algorithm,但是就變得不那麼有趣了。

所以說,我這回真的弄迷糊了,還好老師把我給拉了回來。同時,老師送了我一句金玉良言:

You should keep on going further and further.


希望,我每天都能有新的進展!

No comments: