We introduce a new model for property testing of Boolean functions, which we call distribution-robust testing. Distribution-robust testing is motivated by the hope of designing testers whose output can be trusted even when the underlying probability distribution does not satisfy the assumptions of the tester, while still being more efficient than distribution-free testers that make no assumptions at all.
The purpose of this paper is to perform a broad initial exploration of this new model. In particular, we present a variety of general algorithmic techniques, which we apply to show that several well-studied properties admit distribution-robust testers that are significantly more efficient than their distribution-free counterparts. For example, we obtain constant-query distribution-robust testers for conjunctions, decision lists, and unions of intervals, all of which are known to require significantly more queries in the distribution-free model. These encouraging results suggest a range of questions for future work.