7 papers
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 frame…
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…
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…
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…
Lower Bounds for Convexity Testing
Xi Chen, Anindya De, Shivam Nadimpalli +2
We consider the problem of testing whether an unknown and arbitrary set (given as a black-box membership oracle) is convex, versus -far from…