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 - 2006/11
Y1 - 2006/11
N2 - In property testing, we are given oracle access to a function f, and we wish to 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 domain. 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 query complexity of the property tester.
AB - In property testing, we are given oracle access to a function f, and we wish to 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 domain. 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 query complexity of the property tester.
KW - Information theory
KW - Property testing
UR - http://www.scopus.com/inward/record.url?scp=84855206859&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84855206859&partnerID=8YFLogxK
U2 - 10.1016/j.ic.2006.06.001
DO - 10.1016/j.ic.2006.06.001
M3 - Article
AN - SCOPUS:84855206859
SN - 0890-5401
VL - 204
SP - 1704
EP - 1717
JO - Information and Computation
JF - Information and Computation
IS - 11
ER -