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

--

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
Homepage: http://www.cs.ccu.edu.tw/~lincc
Email: lincc@cs.ccu.edu.tw
Blog: http://ccucclin.blogspot.com/
---

Anonymous said...

Joseph, Chuang-Chieh Lin said...

sublinear的要求不一定要達到，但是能夠sublinear會更好，而且通常他們不看epsilon的。(Rubinfeld教授的回信就是這樣說，他說通常把epsilon當成是一個constant)

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

Right?

Anonymous said...