2
$\begingroup$

There are $\binom{2n}{n} = \frac{4^n}{\sqrt{\pi n}} \cdot (1 - o(1))$ possible $n$-element subsets of a $2n$-element set. Therefore, any data structure storing such a set must use at least $2n - O(\log n)$ bits.

It’s easy to store such a set in $2n$ bits by using a bitvector while getting $O(1)$ membership queries. Is there a way to store such a set in $2n - \omega(1)$ bits, so that membership queries are “fast” for some reasonable definition of “fast?” (E.g. $O(1)$ time, polylog $n$, etc.)

$\endgroup$
9
  • 1
    $\begingroup$ This might not be relevent, but if I'm not mistaken, there is a datastructe that uses $n+o(n)$ space, and answers queries in constant time: en.wikipedia.org/wiki/…. If you allow one sided error, this is also known as static approximate membership query data structure, or a static filter. When the set of elements is not known in advance, and you need to support insertions as well this is called an incremental filter. A classical example of such is Bloom filter. $\endgroup$ Commented Feb 27 at 8:39
  • 1
    $\begingroup$ @TheHolyJoker Actually, this part of the Wikipedia article seems to directly answer the question: en.wikipedia.org/wiki/… . It references doi.org/10.1137/S0097539795294165 and (for support of more operations) doi.org/10.1145/1290672.1290680 . $\endgroup$ Commented Feb 27 at 9:28
  • $\begingroup$ No, wait, it doesn’t work: the error margins are too large. For the case at hand, $B(n,2n)+o(B(n,2n))$ just means the same as $2n+o(n)$, and is likely even larger than $2n$. The bounds in doi.org/10.1145/3357713.3384274 are much better, but still not good enough: $\log\binom{2n}n+\log n+O(\log\log\log\log\log n)$ is about $2n+\frac12\log n$. $\endgroup$ Commented Feb 27 at 10:34
  • $\begingroup$ Further references are in cstheory.stackexchange.com/a/19317 , but I haven’t checked if they are any good. $\endgroup$ Commented Feb 27 at 10:47
  • $\begingroup$ For the record, any algorithm/data structure for this is completely galactic. You'd need on the order of $2^{64}$ bits to save a single 32-bit register compared to the naive full storage. $\endgroup$
    – orlp
    Commented Feb 27 at 22:57

0

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.