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

CREATORXi Chen, William Pires, Toniann Pitassi, Rocco A. Servedio
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE116 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-08987

Browse the full library · About the Tower of Babel