# Approximate (in hamming distance) subset representation

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?

• Have you looked at the filter lower bound of $\log_2 (1/\epsilon)$? That might show a lower bound for your scenario, as well. Commented Jan 17, 2022 at 15:54
• Good point. I removed that part. Commented Jan 18, 2022 at 9:46
• @EmilJeřábek no, I just care about information-theoretic feasibility. Commented Jan 18, 2022 at 19:58
• 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. Commented Jan 18, 2022 at 23:21
• 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|$.) Commented Jan 19, 2022 at 0:16