Monday, November 06, 2006

A question about property testing

Dear Professor Rubinfeld:

I think of a question about property testing. Let me try to describe it
as follows.

As to the paper Spot Checkers, published on JCSS in 2000, we have a tester for testing monotonically increasing of a given sequence of numbers. In this paper, the time complexity is $O(log n/\epsilon)$.

However, $1/\epsilon$ may be $1/n$. Then we will obtain a running time of $O(n\log n)$ yet we can easily test if a sequence of numbers are monotonically increasing in $O(n)$ time.

What is the point of view I misunderstand? Is $\epsilon$ always be viewed as a "fixed-parameter" or a constant?

Thank you for reading this mail.

Sincerely yours,


Think hard, not work hard.
- Professor R. C. T. Lee


Joseph Chuang-Chieh Lin (林莊傑)
Dept. of Computer Science and Information Engineering,
National Chung-Cheng University


Anonymous said...

有一些 survey 是把 property testing 定為和問題本身independent.

以圖為例,如果 epsilon 和點數,邊數,或者 degree 等與 instance 有關的性質是 independnet,則也可以算是一種 tester,未必一定要 sublinear.

然而,還是有些 tester 連這個都不符合。實在是奇怪。

Joseph, Chuang-Chieh Lin said...

還是我搞錯了 :D


Anonymous said...

Ron, D. Property Testing : A Tutorial

Section 1.1 Motivation
``We aim at spending time that is sublinear in or even independent of the size of graph.''

Joseph, Chuang-Chieh Lin said...

Ya..I knew what you mean.

I meant that you should say:

"以圖為例,如果 epsilon 和點數,邊數,或者 degree 等與 instance 『無』關的性質是 independnet,則也可以算是一種 tester,未必一定要 sublinear."

例如:Tester可以是sublinear (ex: O(log n)) 或根本是跟n無關更好(或"最好"),那就可以在某種程度上視為constant time的tester了。最好如此的原因是因為有時候有的問題存在polynomial deterministic algorithm去解決,所以不sublinear簡直是沒搞頭。


Anonymous said...



我是說 epsilon 和某些性質 independnet, 而那些性質和圖 dependnet.

不過我認為不見得 independnet 是很好的結果。譬如epsilon的指數函數。甚至,有時候或許只是看起來 independent...