7 papers · 1 filter
Halfspaces are hard to test with relative error
Xi Chen, Anindya De, Yizhi Huang +3
Several recent works [DHLNSY25, CPPS25a, CPPS25b] have studied a model of property testing of Boolean functions under a \emph{relative-error} criterion. In this model, the distance…
DNF formulas are efficiently testable with relative error
Xi Chen, William Pires, Toniann Pitassi +1
We give a poly-query algorithm for testing whether an unknown and arbitrary function is an -term DNF, in the challenging relative-error fram…
Relative-error unateness testing
Xi Chen, Diptaksho Palit, Kabir Peshawaria +3
The model of relative-error property testing of Boolean functions has been the subject of significant recent research effort [CDH+24][CPPS25a][CPPS25b] In this paper we consider th…
Relative-error monotonicity testing
Xi Chen, Anindya De, Yizhi Huang +4
The standard model of Boolean function property testing is not well suited for testing functions which have few satisfying assignments, since every such function…
Testing Juntas and Junta Subclasses with Relative Error
Xi Chen, William Pires, Toniann Pitassi +1
This papers considers the junta testing problem in a recently introduced ``relative error'' variant of the standard Boolean function property testing model. In relative-error testi…
Relative-error testing of conjunctions and decision lists
Xi Chen, William Pires, Toniann Pitassi +1
We study the relative-error property testing model for Boolean functions that was recently introduced in the work of Chen et al. (SODA 2025). In relative-error testing, the testing…