Alladi Ramakrishnan Hall
Support size estimation - Power of conditioning
Gunjan Kumar
National University of Singapore
We consider the problem of estimating the support size of a distribution $D$. Our investigations are pursued through the lens of distribution testing and seek to understand the power of conditional sampling, wherein one is allowed to query the given distribution conditioned on an arbitrary subset $S$. The primary contribution of this work is to introduce a new approach to lower bounds for conditional sampling models that rely on using powerful tools from information theory, communication complexity, and Bayesian statistics.
Done