School of Technology and Computer Science Seminars
On the Power of Conditional Samples in Distribution Testing
by Dr. Sourav Chakraborty (Chennai Mathematical Institute, Chennai)
Thursday, November 7, 2013
from
to
(Asia/Kolkata)
at Colaba Campus ( AG-80 )
at Colaba Campus ( AG-80 )
Description |
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$ of the domain, and outputs a random sample $i\in S$ drawn according to $\mu$, conditioned on $S$ (and independently of all prior samples). The conditional-sampling oracle is a natural generalization of the ordinary sampling oracle in which $S$ always equals the whole domain. We show that with the conditional-sampling oracle, testing uniformity, testing identity to a known distribution, and testing any label-invariant property of distributions is easier than with the ordinary sampling oracle. On the other hand, we also show that for some distribution properties the sample-complexity remains near-maximal even with conditional sampling. One can use conditional sampling for various real life problems also (this is a joint work with Eldar Fischer, Yonatan Goldhirsh and Arie Matsliah). |