On the power of conditional samples in distribution testing (Q6829129)

A conditional-sampling oracle for an unknown probability distribution \(D\) on \([n] := \{1, \dots, n\}\) allows to sample for any \(S \subseteq [n]\) an element from \(S\) according to the conditional distribution \((D|S)\). It is thus a generalization of the ordinary sampling oracle, which refers to the case \(S = [n]\).\N\N\N\NIn this work, it is shown that conditional-sampling oracles can be significantly more powerful than ordinary sampling oracles. For example, the property of uniformity can be tested with a constant number of conditional samples, whereas \(\Omega(\sqrt n)\) ordinary samples are necessary. In fact, not the full strength of the conditional-sampling oracle is needed, but it suffices to use ordinary samples and samples conditional on constant-size sets \(S\).\N\N\N\NIn contrast to this result, also properties are presented for which conditional-sampling oracles need \(\Omega(n)\) samples and thus are not significantly stronger than ordinary ones.