Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR04-068 | 13th August 2004 00:00

Information Theory in Property Testing and Monotonicity Testing in Higher Dimension


Authors: Nir Ailon, Bernard Chazelle
Publication: 16th August 2004 16:59
Downloads: 1142


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

ISSN 1433-8092 | Imprint