Dear Professor Rubinfeld:
I think of a question about property testing. Let me try to describe it
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.
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