DNF formulas are efficiently testable with relative error
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918299992850432 |
|---|---|
| author | Chen, Xi Pires, William Pitassi, Toniann Servedio, Rocco A. |
| author_facet | Chen, Xi Pires, William Pitassi, Toniann Servedio, Rocco A. |
| contents | We give a poly$(s,1/ε)$-query algorithm for testing whether an unknown and arbitrary function $f: \{0,1\}^n \to \{0,1\}$ is an $s$-term DNF, in the challenging relative-error framework for Boolean function property testing that was recently introduced and studied in a number of works [CDH+25b, CPPS25a, CPPS25b, CDH+25a]. This gives the first example of a rich and natural class of functions which may depend on a super-constant number of variables and yet is efficiently testable in the relative-error model with constant query complexity.
A crucial new ingredient enabling our approach is a novel decomposition of any $s$-term DNF formula into ``local clusters'' of terms. Our results demonstrate that this new decomposition can be usefully exploited for algorithms even when the $s$-term DNF is not explicitly given; we believe that this decomposition may have applications in other contexts. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_16076 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | DNF formulas are efficiently testable with relative error Chen, Xi Pires, William Pitassi, Toniann Servedio, Rocco A. Computational Complexity Data Structures and Algorithms We give a poly$(s,1/ε)$-query algorithm for testing whether an unknown and arbitrary function $f: \{0,1\}^n \to \{0,1\}$ is an $s$-term DNF, in the challenging relative-error framework for Boolean function property testing that was recently introduced and studied in a number of works [CDH+25b, CPPS25a, CPPS25b, CDH+25a]. This gives the first example of a rich and natural class of functions which may depend on a super-constant number of variables and yet is efficiently testable in the relative-error model with constant query complexity. A crucial new ingredient enabling our approach is a novel decomposition of any $s$-term DNF formula into ``local clusters'' of terms. Our results demonstrate that this new decomposition can be usefully exploited for algorithms even when the $s$-term DNF is not explicitly given; we believe that this decomposition may have applications in other contexts. |
| title | DNF formulas are efficiently testable with relative error |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2601.16076 |