Information theory in property testing and monotonicity testing in higher dimension

Nir Ailon; Bernard Chazelle

doi:10.1016/j.ic.2006.06.001

Information theory in property testing and monotonicity testing in higher dimension

Nir Ailon
, Bernard Chazelle

Research output: Contribution to journal › Article › peer-review

55 Scopus citations

Abstract

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.

Original language	English (US)
Pages (from-to)	1704-1717
Number of pages	14
Journal	Information and Computation
Volume	204
Issue number	11
DOIs	https://doi.org/10.1016/j.ic.2006.06.001
State	Published - Nov 2006
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Information Systems
Computer Science Applications
Computational Theory and Mathematics

Keywords

Information theory
Property testing

Access to Document

10.1016/j.ic.2006.06.001

Cite this

@article{fac07e204d6e43bca4d68056e32c1cad,

title = "Information theory in property testing and monotonicity testing in higher dimension",

abstract = "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.",

keywords = "Information theory, Property testing",

author = "Nir Ailon and Bernard Chazelle",

note = "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).",

year = "2006",

month = nov,

doi = "10.1016/j.ic.2006.06.001",

language = "English (US)",

volume = "204",

pages = "1704--1717",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Elsevier Inc.",

number = "11",

}

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 - https://www.scopus.com/pages/publications/84855206859

UR - https://www.scopus.com/pages/publications/84855206859#tab=citedBy

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 -

Information theory in property testing and monotonicity testing in higher dimension

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this