Distribution-Free junta testing

Zhengyang Liu; Xi Chen; Rocco A. Servedio; Ying Sheng; Jinyu Xie

doi:10.1145/3188745.3188842

Distribution-Free junta testing

Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, Jinyu Xie

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

11 Citations (Scopus)

Abstract

We study the problem of testing whether an unknown n-variable Boolean function is a k-junta in the distribution-free property testing model, where the distance between functions is measured with respect to an arbitrary and unknown probability distribution over {0, 1}ⁿ. Our first main result is that distribution-free k-junta testing can be performed, with one-sided error, by an adaptive algorithm that uses Õ (k²)/ queries (independent of n). Complementing this, our second main result is a lower bound showing that any nonadaptive distribution-free k-junta testing algorithm must make Ω(2^k/³) queries even to test to accuracy = 1/3. These bounds establish that while the optimal query complexity of non-adaptive k-junta testing is 2^Θ(k), for adaptive testing it is poly(k), and thus show that adaptivity provides an exponential improvement in the distribution-free query complexity of testing juntas.

Original language	English
Title of host publication	STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
Editors	Monika Henzinger, David Kempe, Ilias Diakonikolas
Publisher	Association for Computing Machinery
Pages	65-73
Number of pages	9
ISBN (Electronic)	9781450355599
DOIs	https://doi.org/10.1145/3188745.3188842
Publication status	Published - 20 Jun 2018
Externally published	Yes
Event	50th Annual ACM Symposium on Theory of Computing, STOC 2018 - Los Angeles, United States Duration: 25 Jun 2018 → 29 Jun 2018

Publication series

Name	Proceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)	0737-8017

Conference

Conference	50th Annual ACM Symposium on Theory of Computing, STOC 2018
Country/Territory	United States
City	Los Angeles
Period	25/06/18 → 29/06/18

Keywords

Distribution-free testing
Juntas
Property testing

Access to Document

10.1145/3188745.3188842

Cite this

Liu, Z., Chen, X., Servedio, R. A., Sheng, Y., & Xie, J. (2018). Distribution-Free junta testing. In M. Henzinger, D. Kempe, & I. Diakonikolas (Eds.), STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (pp. 65-73). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/3188745.3188842

@inproceedings{8b3fc38dc31244bb8122ac8cdb4e63de,

title = "Distribution-Free junta testing",

abstract = "We study the problem of testing whether an unknown n-variable Boolean function is a k-junta in the distribution-free property testing model, where the distance between functions is measured with respect to an arbitrary and unknown probability distribution over {0, 1}n. Our first main result is that distribution-free k-junta testing can be performed, with one-sided error, by an adaptive algorithm that uses {\~O} (k2)/ queries (independent of n). Complementing this, our second main result is a lower bound showing that any nonadaptive distribution-free k-junta testing algorithm must make Ω(2k/3) queries even to test to accuracy = 1/3. These bounds establish that while the optimal query complexity of non-adaptive k-junta testing is 2Θ(k), for adaptive testing it is poly(k), and thus show that adaptivity provides an exponential improvement in the distribution-free query complexity of testing juntas.",

keywords = "Distribution-free testing, Juntas, Property testing",

author = "Zhengyang Liu and Xi Chen and Servedio, {Rocco A.} and Ying Sheng and Jinyu Xie",

note = "Publisher Copyright: {\textcopyright} 2018 Copyright held by the owner/author(s).; 50th Annual ACM Symposium on Theory of Computing, STOC 2018 ; Conference date: 25-06-2018 Through 29-06-2018",

year = "2018",

month = jun,

day = "20",

doi = "10.1145/3188745.3188842",

language = "English",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "65--73",

editor = "Monika Henzinger and David Kempe and Ilias Diakonikolas",

booktitle = "STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing",

}

Liu, Z, Chen, X, Servedio, RA, Sheng, Y & Xie, J 2018, Distribution-Free junta testing. in M Henzinger, D Kempe & I Diakonikolas (eds), STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, pp. 65-73, 50th Annual ACM Symposium on Theory of Computing, STOC 2018, Los Angeles, United States, 25/06/18. https://doi.org/10.1145/3188745.3188842

Distribution-Free junta testing. / Liu, Zhengyang; Chen, Xi; Servedio, Rocco A. et al.
STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. ed. / Monika Henzinger; David Kempe; Ilias Diakonikolas. Association for Computing Machinery, 2018. p. 65-73 (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Distribution-Free junta testing

AU - Liu, Zhengyang

AU - Chen, Xi

AU - Servedio, Rocco A.

AU - Sheng, Ying

AU - Xie, Jinyu

PY - 2018/6/20

Y1 - 2018/6/20

N2 - We study the problem of testing whether an unknown n-variable Boolean function is a k-junta in the distribution-free property testing model, where the distance between functions is measured with respect to an arbitrary and unknown probability distribution over {0, 1}n. Our first main result is that distribution-free k-junta testing can be performed, with one-sided error, by an adaptive algorithm that uses Õ (k2)/ queries (independent of n). Complementing this, our second main result is a lower bound showing that any nonadaptive distribution-free k-junta testing algorithm must make Ω(2k/3) queries even to test to accuracy = 1/3. These bounds establish that while the optimal query complexity of non-adaptive k-junta testing is 2Θ(k), for adaptive testing it is poly(k), and thus show that adaptivity provides an exponential improvement in the distribution-free query complexity of testing juntas.

AB - We study the problem of testing whether an unknown n-variable Boolean function is a k-junta in the distribution-free property testing model, where the distance between functions is measured with respect to an arbitrary and unknown probability distribution over {0, 1}n. Our first main result is that distribution-free k-junta testing can be performed, with one-sided error, by an adaptive algorithm that uses Õ (k2)/ queries (independent of n). Complementing this, our second main result is a lower bound showing that any nonadaptive distribution-free k-junta testing algorithm must make Ω(2k/3) queries even to test to accuracy = 1/3. These bounds establish that while the optimal query complexity of non-adaptive k-junta testing is 2Θ(k), for adaptive testing it is poly(k), and thus show that adaptivity provides an exponential improvement in the distribution-free query complexity of testing juntas.

KW - Distribution-free testing

KW - Juntas

KW - Property testing

UR - http://www.scopus.com/inward/record.url?scp=85049871996&partnerID=8YFLogxK

U2 - 10.1145/3188745.3188842

DO - 10.1145/3188745.3188842

M3 - Conference contribution

AN - SCOPUS:85049871996

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 65

EP - 73

BT - STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

A2 - Henzinger, Monika

A2 - Kempe, David

A2 - Diakonikolas, Ilias

PB - Association for Computing Machinery

T2 - 50th Annual ACM Symposium on Theory of Computing, STOC 2018

Y2 - 25 June 2018 through 29 June 2018

ER -

Distribution-Free junta testing

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this