The Power of an Example: Hidden Set Size Approximation Using Group Queries and Conditional Sampling

Dana Ron, Gilad Tsur

We study a basic problem of approximating the size of an unknown set $S$ in a known universe $U$. We consider two versions of the problem. In both versions the algorithm can specif…