Relative-error monotonicity testing

The standard model of Boolean function property testing is not well suited for testing textitsparse functions which have few satisfying assignments, since every such function is close (in the usual Hamming distance metric) to the constant-0 function. In this work we propose and investigate a new model for property testing of Boolean functions, called textitrelative-error testing, which provides a natural framework for testing sparse functions. This new model defines the distance between two functions f, g: 0,1n → 0,1 to be textsfreldist(f,g) := frac|f-1(1) triangle g-1(1)| |f-1(1)|. This is a more demanding distance measure than the usual Hamming distance |f-1(1) triangle g-1(1)|/2n when |f-1(1)| ll 2n; to compensate for this, algorithms in the new model have access both to a black-box oracle for the function f being tested and to a source of independent uniform satisfying assignments of f. In this paper we first give a few general results about the relative-error testing model; then, as our main technical contribution, we give a detailed study of algorithms and lower bounds for relative-error testing of textitmonotone Boolean functions. We give upper and lower bounds which are parameterized by N=|f-1(1)|, the sparsity of the function f being tested. Our results show that there are interesting differences between relative-error monotonicity testing of sparse Boolean functions, and monotonicity testing in the standard model. These results motivate further study of the testability of Boolean function properties in the relative-error model.