2025/11/09 by Xi Chen, Anindya De, Chen, Xi +9
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #Software Testing and Debugging Techniques
paper · pdf · doi:10.48550/arxiv.2511.06171
openalex publication_date 2025/11/09 · openalex created_date 2025/11/12 · openalex updated_date 2026/07/28
Several recent works [DHLNSY25, CPPS25a, CPPS25b] have studied a model of property testing of Boolean functions under a relative-error criterion. In this model, the distance from a target function f: \0,1\n → \0,1\ that is being tested to a function g is defined relative to the number of inputs x for which f(x)=1; moreover, testing algorithms in this model have access both to a black-box oracle for f and to independent uniform satisfying assignments of f. The motivation for this model is that it provides a natural framework for testing sparse Boolean functions that have few satisfying assignments, analogous to well-studied models for property testing of sparse graphs. The main result of this paper is a lower bound for testing halfspaces (i.e., linear threshold functions) in the relative error model: we show that Ω(log n) oracle calls are required for any relative-error halfspace testing algorithm over the Boolean hypercube \0,1\n. This stands in sharp contrast both with the constant-query testability (independent of n) of halfspaces in the standard model [MORS10], and with the positive results for relative-error testing of many other classes given in [DHLNSY25, CPPS25a, CPPS25b]. Our lower bound for halfspaces gives the first example of a well-studied class of functions for which relative-error testing is provably more difficult than standard-model testing.