Information theory in property testing and monotonicity testing in higher dimension

Nir Ailon; Bernard Chazelle

doi:10.1007/978-3-540-31856-9_36

Information theory in property testing and monotonicity testing in higher dimension

Nir Ailon
, Bernard Chazelle

Research output: Contribution to journal › Conference article › peer-review

2 Scopus citations

Abstract

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.

Original language	English (US)
Pages (from-to)	434-447
Number of pages	14
Journal	LECTURE NOTES IN COMPUTER SCIENCE
Volume	3404
DOIs	https://doi.org/10.1007/978-3-540-31856-9_36
State	Published - 2005
Externally published	Yes
Event	22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS 2005 - Stuttgart, Germany Duration: Feb 24 2005 → Feb 26 2005

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-31856-9_36

Cite this

@article{f49bfc33fe534cff8a413c2df2a94930,

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

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

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).; 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS 2005 ; Conference date: 24-02-2005 Through 26-02-2005",

year = "2005",

doi = "10.1007/978-3-540-31856-9\_36",

language = "English (US)",

volume = "3404",

pages = "434--447",

journal = "LECTURE NOTES IN COMPUTER SCIENCE",

issn = "0302-9743",

publisher = "Springer Science and Business Media Deutschland GmbH",

}

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

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

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 -

Information theory in property testing and monotonicity testing in higher dimension

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this