2026-07-25T09:51:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23429 2025-10-02T12:54:53Z ddc:004 open_access

Relative-Error Testing of Conjunctions and Decision Lists Chen, Xi Pires, William Pitassi, Toniann Servedio, Rocco A. Property Testing Relative Error We study the relative-error property testing model for Boolean functions that was recently introduced in the work of [X. Chen et al., 2025]. In relative-error testing, the testing algorithm gets uniform random satisfying assignments as well as black-box queries to f, and it must accept f with high probability whenever f has the property that is being tested and reject any f that is relative-error far from having the property. Here the relative-error distance from f to a function g is measured with respect to |f^{-1}(1)| rather than with respect to the entire domain size 2ⁿ as in the Hamming distance measure that is used in the standard model; thus, unlike the standard model, relative-error testing allows us to study the testability of sparse Boolean functions that have few satisfying assignments. It was shown in [X. Chen et al., 2025] that relative-error testing is at least as difficult as standard-model property testing, but for many natural and important Boolean function classes the precise relationship between the two notions is unknown. In this paper we consider the well-studied and fundamental properties of being a conjunction and being a decision list. In the relative-error setting, we give an efficient one-sided error tester for conjunctions with running time and query complexity O(1/ε). Secondly, we give a two-sided relative-error Õ(1/ε) tester for decision lists, matching the query complexity of the state-of-the-art algorithm in the standard model [Nader H. Bshouty, 2020; I. Diakonikolas et al., 2007]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xi Chen and William Pires and Toniann Pitassi and Rocco A. Servedio 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.52 urn:nbn:de:0030-drops-234291 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.52 eng https://creativecommons.org/licenses/by/4.0/legalcode