Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR19-088 | 16th June 2019 18:32

On the Complexity of Estimating the Effective Support Size

RSS-Feed




TR19-088
Authors: Oded Goldreich
Publication: 16th June 2019 18:33
Downloads: 238
Keywords: 


Abstract:

Loosely speaking, the effective support size of a distribution is the size of the support of a distribution that is close to it (in totally variation distance).
We study the complexity of estimating the effective support size of an unknown distribution when given samples of the distributions as well as an evaluation oracle (which returns the probability that the queried element appears in the distribution).
In this context, we present several algorithms that exhibit a trade-off between the quality of the approximation and the complexity of obtaining it, and leave open the question of their optimality.



ISSN 1433-8092 | Imprint