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

47 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

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: nailon@cs.princeton.edu (N. Ailon), chazelle@cs.princeton.edu (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: nailon@cs.princeton.edu (N. Ailon), chazelle@cs.princeton.edu (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 -

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