Relative-error testing of conjunctions and decision lists
Xi Chen, William Pires, Toniann Pitassi, Rocco A. Servedio · 2025
Read Relative-error testing of conjunctions and decision lists by Xi Chen, William Pires, Toniann Pitassi, Rocco A. Servedio (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-08987.txt.
Description
Xi Chen, William Pires, Toniann Pitassi and Rocco Servedio test Boolean formulas under a relative-error model, in their 2025 arXiv paper. Property testing asks whether a function has a given form, using few queries. Relative-error testing suits sparse functions: the tester sees random satisfying inputs and measures distance relative to how many there are, not the whole domain.
For conjunctions they give a one-sided tester whose cost depends only on the accuracy parameter. For decision lists they give a two-sided tester matching the best known query cost from the standard model. The results narrow the gap between the two testing models for two fundamental function classes.
Catalog record
| CREATOR | Xi Chen, William Pires, Toniann Pitassi, Rocco A. Servedio |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 116 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-08987