<p><strong>Lemma:</strong> Consider two sets <span class="math-container">$B ⊆ U$</span>, where <span class="math-container">$n = |U|$</span>. Let <span class="math-container">$ξ, γ ∈ (0, 1)$</span> be parameters, such that
<span class="math-container">$γ &lt; 1/ \log n$</span>. Assume that one is given an access to a membership oracle that, given an element <span class="math-container">$x ∈ U$</span>,
returns whether or not <span class="math-container">$x ∈ B$</span>. Then, one can compute an estimate <span class="math-container">$s$</span>, such that <span class="math-container">$(1 − ξ)|B| ≤ s ≤
(1 + ξ)|B|$</span>, and computing this estimate requires <span class="math-container">$O((n/ |B|)ξ^{−2}
\log γ^{−1}
)$</span> oracle queries. The returned
estimate is correct with probability <span class="math-container">$\ge 1- \gamma$</span>.</p>
<p>The above lemma can be found in <a href="https://arxiv.org/pdf/1711.07567.pdf" rel="nofollow noreferrer">Link</a> (Page 12, lemma 2.8).</p>
<p>Assume that we are given <span class="math-container">$t$</span> sets <span class="math-container">$B_1,B_2,\ldots,B_t \subseteq U$</span> (assume that <span class="math-container">$|B_i|=|B|$</span> for all <span class="math-container">$i\in [t]$</span>). We want to estimate the size of the all sets. The most natural way is to call the above lemma <span class="math-container">$t$</span> number of times, which results in time complexity <span class="math-container">$O(t(n/ |B|)ξ^{−2}
\log γ^{−1}
)$</span>.</p>
<p><strong>Question:</strong> Is there any algorithm which solve the above problem in time faster than <span class="math-container">$O(t(n/ |B|)ξ^{−2}
\log γ^{−1}
)$</span>.  Please refer any material which studies these kind of problems.</p>

CC BY-SA 4.0
2022-11-02T15:09:23.417Z
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?)
Neal Young
CC BY-SA 4.0
2022-11-02T15:25:55.273Z
@Neal Young There will be $t$ many oracles. To tell which of the sets contain the element we need to call each oracle one by one.
Com
CC BY-SA 4.0
2022-11-02T17:50:00.303Z
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?
Neal Young
CC BY-SA 4.0
2022-11-03T02:33:47.997Z
@ Neal Young, It will be surprising. The problem you have described seems to be more general than the problem I am trying to solve as in my case universe is same. So I am expecting there may be way to solve the problem efficiently (may be using parallel computation or by doing some preprocessing on the universe). What are some reasonable assumptions under which one can come up with a faster algorithm. Is it like assuming an oracle which tell you which of the sets contain the element?
Com
CC BY-SA 4.0
2022-11-03T11:51:01.043Z
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.
Neal Young
CC BY-SA 4.0
2022-11-03T13:47:47.530Z
@Neal Young Yes.
Com
CC BY-SA 4.0
2022-11-03T17:43:52.403Z
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).
Neal Young
CC BY-SA 4.0
2022-11-04T09:50:22.530Z
@Neal Young The asked question is motivated from the paper given in the link. About assumptions it is not clear to me what kind of assumptions are reasonable in this context.
Com
CC BY-SA 4.0
2022-11-04T12:29:55.023Z
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!
Neal Young
CC BY-SA 4.0
2022-11-20T06:36:49.283Z
@Neal Young Thanks for the advice. I have only access to the membership oracle.
Com
<reference-request><set-theory>
Faster algorithms to estimate the subset sizes
Com
# Faster algorithms to estimate the subset sizes

(Asked by: username_0 on 2022-11-02)

**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](https://arxiv.org/pdf/1711.07567.pdf) (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.

**Tags:** reference-request, set-theory
> **Comments:**
> **username_1**: 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?)  
> **username_0**: @Neal Young There will be $t$ many oracles. To tell which of the sets contain the element we need to call each oracle one by one.  
> **username_1**: 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?  
> **username_0**: @ Neal Young, It will be surprising. The problem you have described seems to be more general than the problem I am trying to solve as in my case universe is same. So I am expecting there may be way to solve the problem efficiently (may be using parallel computation or by doing some preprocessing on the universe). What are some reasonable assumptions under which one can come up with a faster algorithm. Is it like assuming an oracle which tell you which of the sets contain the element?  
> **username_1**: 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.  
> **username_0**: @Neal Young Yes.  
> **username_1**: 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).  
> **username_0**: @Neal Young The asked question is motivated from the paper given in the link. About assumptions it is not clear to me what kind of assumptions are reasonable in this context.  
> **username_1**: 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!  
> **username_0**: @Neal Young Thanks for the advice. I have only access to the membership oracle.  

---

## 0 answers

