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.

  • $\begingroup$ 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?) $\endgroup$
    – Neal Young
    Nov 2, 2022 at 15:09
  • 1
    $\begingroup$ 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? $\endgroup$
    – Neal Young
    Nov 2, 2022 at 17:50
  • 1
    $\begingroup$ 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. $\endgroup$
    – Neal Young
    Nov 3, 2022 at 11:51
  • 1
    $\begingroup$ 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). $\endgroup$
    – Neal Young
    Nov 3, 2022 at 17:43
  • 1
    $\begingroup$ 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! $\endgroup$
    – Neal Young
    Nov 4, 2022 at 12:29


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.