# Faster algorithms to estimate the subset sizes

Lemma: Consider two sets $$B ⊆ U$$, where $$n = |U|$$. Let $$ξ, γ ∈ (0, 1)$$ be parameters, such that $$γ < 1/ \log n$$. Assume that one is given an access to a membership oracle that, given an element $$x ∈ U$$, returns whether or not $$x ∈ B$$. Then, one can compute an estimate $$s$$, such that $$(1 − ξ)|B| ≤ s ≤ (1 + ξ)|B|$$, and computing this estimate requires $$O((n/ |B|)ξ^{−2} \log γ^{−1} )$$ oracle queries. The returned estimate is correct with probability $$\ge 1- \gamma$$.

The above lemma can be found in Link (Page 12, lemma 2.8).

Assume that we are given $$t$$ sets $$B_1,B_2,\ldots,B_t \subseteq U$$ (assume that $$|B_i|=|B|$$ for all $$i\in [t]$$). We want to estimate the size of the all sets. The most natural way is to call the above lemma $$t$$ number of times, which results in time complexity $$O(t(n/ |B|)ξ^{−2} \log γ^{−1} )$$.

Question: Is there any algorithm which solve the above problem in time faster than $$O(t(n/ |B|)ξ^{−2} \log γ^{−1} )$$. Please refer any material which studies these kind of problems.

• What kind of oracle do you assume? (E.g., given an element, will a single call to the oracle tell you which of the sets contain the element?) Nov 2, 2022 at 15:09
• Why would you expect any improvement to be possible? Given, say, $n$ completely independent instances $(B_1, U_1), (B_2, U_2), \ldots, (B_n, U_n)$ of the original problem (where the $U_i$'s are pairwise disjoint, and have $|U_i|=n$, say), you could reduce the problem of solving them all to a single instance of your problem, namely $(B_1, B_2, \ldots, B_n, U)$ where $U=\bigcup_i U_i$, then solve that single instance to solve all $n$ given instances. Wouldn't it be surprising if you could somehow do that faster than solving all original instances independently? Nov 2, 2022 at 17:50
• But the reduced instance $(B_1, \ldots, B_n, U)$ has just a single universe, as in your problem. Your problem as stated does not preclude the $B_i$'s from being pairwise-disjoint, say. Nov 3, 2022 at 11:51
• It seems to me that to get any improvement you'll have to make some explicit changes in the question. E.g., add some assumptions, or change the metric that you are using from worst-case analysis to something else. Without that I don't think anything is possible. Maybe it would help for you to explain the context (e.g. why you need a solution to this problem). Nov 3, 2022 at 17:43
• Well, my advice (not that you asked for it) is that you might have more luck here if you can explain in the post what kinds of assumptions you might be interested in. As the question is now, it (a) doesn't mention that you are willing to consider any restrictions on the problem (without which, almost certainly, nothing is possible), and (b) doesn't say anything about which restrictions you might be willing to consider (which leaves the reader to guess). Anyhow, good luck! Nov 4, 2022 at 12:29