2
$\begingroup$

Let us have a set $S$ and a subset $T \subseteq S$. I want to find an approximate representation of $T$, i.e. I want to represent (exactly) a set $T'$ that is close to $T$. That is, I want the symmetric difference $|T \triangle T'| \leq \epsilon |T|$. I want the representation to be as small as possible.

Formally speaking, I want to have functions $f: 2^S \rightarrow \{0,1\}^*$ and $g: \{0,1\}^* \rightarrow 2^S$ such that $f(T)$ has as few bits as possible (i.e. it is as slowly growing a function of $|T|$ as possible) and $g^{-1}(f(T)) \triangle T \leq \epsilon |T|$.

If I was fine with an error of $\epsilon |S|$ then I could use a bloom filter or one of the similar data structures. However, I am not aware of similar data structures for "relative" approximation. I suspect that nothing non-trivial is possible unless $|T| \approx |S|$. But is this correct?

Improve this question
$\endgroup$
7
  • $\begingroup$ Have you looked at the filter lower bound of $\log_2 (1/\epsilon)$? That might show a lower bound for your scenario, as well. $\endgroup$
    – jbapple
    Jan 17, 2022 at 15:54
  • $\begingroup$ Good point. I removed that part. $\endgroup$
    – user2316602
    Jan 18, 2022 at 9:46
  • 1
    $\begingroup$ @EmilJeřábek no, I just care about information-theoretic feasibility. $\endgroup$
    – user2316602
    Jan 18, 2022 at 19:58
  • 2
    $\begingroup$ I think, by, say, Turan's theorem, letting $n=|S|$, for all $k\le n/4$ and $\epsilon\le 1/4$, you can find a collection $I$ of size-$k$ subsets of $S$ such that every pair $T, T'\in I$ has Hamming distance at least $2\epsilon k$, and $I$ has size at least $\exp(\Theta(k\log n/k))$. No two sets $T, T'$ in $I$ can have $f(T)=f(T')$, implying that any $f$ must have at least $\exp(\Theta(k\log n/k))$ distinct outputs for these sets, so that most sets $T$ in $I$ have $|f(T)| = \Omega(k\log n/k)$. So you can save at best an $O(1)$ factor compared to representing all size-$k$ sets naively. $\endgroup$
    – Neal Young
    Jan 18, 2022 at 23:21
  • 1
    $\begingroup$ BTW is there something "non-trivial possible" when $|T|\approx |S|$? (One trivial thing seems to be to represent $T$ via the complement $S\setminus T$, so I don't see why $|T|\approx |S|$ is much different than $|T| \ll |S|$.) $\endgroup$
    – Neal Young
    Jan 19, 2022 at 0:16

0

Reset to default

Your Answer

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