TY - JOUR
T1 - Information theory in property testing and monotonicity testing in higher dimension
AU - Ailon, Nir
AU - Chazelle, Bernard
N1 - Funding Information:
This work was supported in part by NSF Grant CCR-0306283 and ARO Grant DAAH04-96-1-0181. ∗ Corresponding author. Present address: Ben Gurion University of the Negev, Department of Electrical and Computer Engineering, 84105, Beer Sheva, Israel. E-mail addresses: [email protected] (N. Ailon), [email protected] (B. Chazelle).
PY - 2005
Y1 - 2005
N2 - 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 ε-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.
AB - 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 ε-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.
UR - http://www.scopus.com/inward/record.url?scp=24144498384&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=24144498384&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-31856-9_36
DO - 10.1007/978-3-540-31856-9_36
M3 - Conference article
AN - SCOPUS:24144498384
SN - 0302-9743
VL - 3404
SP - 434
EP - 447
JO - LECTURE NOTES IN COMPUTER SCIENCE
JF - LECTURE NOTES IN COMPUTER SCIENCE
T2 - 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS 2005
Y2 - 24 February 2005 through 26 February 2005
ER -