Distribution Testing in the Presence of Arbitrarily Dominant Noise with Verification Queries

We study distribution testing without direct access to a source of relevant data, but rather to a highly contaminated one, from which only a tiny fraction (e.g. 1%) is relevant. To enable this, we introduce the following verification query model. The goal is to perform a statistical task on distribution \(p\) given sample access to a mixture \(r = \lambda p + (1-\lambda)q\) and the ability to query whether a sample \(x \sim r\) was generated by \(p\) (relevant) or by \(q\) (irrelevant). This captures scenarios where it is cheap to acquire data from a massive pool, but expensive to verify whether it is of interest for the specific task. In general, if \(m_0\) clean samples from \(p\) suffice for a task, then \(O(m_0/\lambda)\) samples and verification queries trivially suffice in our model. We ask, are there tasks for which the number of queries can be significantly reduced?