Tata Institute of Fundamental Research
On the Power of Conditional Samples in Distribution Testing
Seminar
Speaker:
Dr. Sourav Chakraborty (Chennai Mathematical Institute (CMI)
Plot No. H1 SIPCOT IT Park
Padur PO
Siruseri 603 103)
Organiser:
Arkadev Chattopadhyay
Date:
Thursday, 7 Nov 2013, 16:00 to 17:00
Venue:
AG-80
(Scan to add to calendar)
Abstract:
Abstract: 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).
| Speaker: | Dr. Sourav Chakraborty (Chennai Mathematical Institute (CMI) Plot No. H1 SIPCOT IT Park Padur PO Siruseri 603 103) |
| Organiser: | Arkadev Chattopadhyay |
| Date: | Thursday, 7 Nov 2013, 16:00 to 17:00 |
| Venue: | AG-80 |
(Scan to add to calendar)
Abstract:
Abstract: 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).
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).