Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR04-068 | 13th August 2004 00:00

#### Information Theory in Property Testing and Monotonicity Testing in Higher Dimension

TR04-068
Authors: Nir Ailon, Bernard Chazelle
Publication: 16th August 2004 16:59
In general property testing, we are given oracle access to a function $f$, and we wish to randomly test if the function satisfies a given property $P$, or it is $\epsilon$-far from having that property. In a more general setting, the domain on which the function is defined is equipped with a probability distribution, which assigns different weight to different elements in the distance function. This paper relates the complexity of testing the monotonicity of a function over the $d$-dimensional cube to the Shannon entropy of the underlying distribution. We provide an improved upper bound on the property tester query complexity and we finetune the exponential dependence on the dimension $d$.