2026-08-18T22:51:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10824 2024-03-06T10:46:48Z ddc:004 open_access

Almost Optimal Distribution-Free Junta Testing Bshouty, Nader H. Distribution-free property testing k-Junta We consider 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. Chen, Liu, Servedio, Sheng and Xie [Zhengyang Liu et al., 2018] showed that the distribution-free k-junta testing can be performed, with one-sided error, by an adaptive algorithm that makes O~(k^2)/epsilon queries. In this paper, we give a simple two-sided error adaptive algorithm that makes O~(k/epsilon) queries. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nader H. Bshouty 2019 Is Part Of LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2019.2 urn:nbn:de:0030-drops-108249 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.2 eng https://creativecommons.org/licenses/by/3.0/legalcode