For a property P and a sub-property P', we say that P is P'-partially testable with q queries if there exists an algorithm that distinguishes, with high probability, inputs in P' from inputs \epsilon-far from P by using q queries. There are natural properties that require many queries to test, ... more >>>

In this paper we define and examine the power of the conditional-sampling oracle in the context of distribution-property testing. The conditional-sampling oracle for a discrete distribution \mu takes as input a subset S \subset [n] of the domain, and outputs a random sample i \in S drawn according to \mu, ... more >>>