Given a set $\cal N$ of $N$ objects, we seek to attribute a code, i.e., a binary sequence, to each of them to achieve the following objective of being capable to select any subset ${\cal S}\subseteq {\cal N}$ of objects with minimal communication cost. To select a set of objects, we need to broadcast a message containing a set of positions in the binary sequence and their values. All the objects matching the broadcast message are selected. For example, consider a system of $3$ objects with codes $001,000,111$, respectively. If we want to slect the first two objects, we can broadcast $\{position=1,value=0\}$ so that only the first two objects match. My problem is to design a coding scheme of length $o(N)$ (ideally $O(\log N)$) such that for any subset of target objects, we only need to broadcast an $O(1)$-length message to select them.
-
2$\begingroup$ There are $2^N$ subsets $S$ of a set of $N$ objects. To select an arbitrary one of these with a constant length message and codes of length $\log N$ seems optimistic to me. $\endgroup$– Gerry MyersonJul 17, 2022 at 5:12
-
$\begingroup$ What about allowing ${\cal O}(\log N)$ message length $\endgroup$– lchenJul 17, 2022 at 5:43
1 Answer
Suppose that there was a code $\mathcal{E}: \mathcal{N} \rightarrow \{0,1\}^{\omega(1)}$ that achieved this condition; in particular, we have two types of messages $p \in \mathcal{P} \subset \{0,1,...d-1\}^c$ (i.e., positions) and $v \in \mathcal{V} \subset \{0,1\}^c$ (i.e., values) such that $$ \mathcal{S}(p,v) = \{ x \in \mathcal{N} \ | \ \mathcal{E}(x)_{p_0}=v_0,\dots,\mathcal{E}(x)_{p_{c-1}}=v_{c-1}\} $$ defines the set you want to select for some constant $c$. Because the length of $p$ must be $\mathcal{O}(1)$, we must have $d = O(1)$ as well (after some relabeling for the positions that are not used).
In order to achieve this, we must have that the function $$ \mathcal{S} : \mathcal{P} \times \mathcal{V} \rightarrow 2^{\mathcal{N}} $$ is bijective and in particular, we must have $$ 2^{c(1+\log d)} \geq |\mathcal{P} \times \mathcal{V}| \geq |2^{\mathcal{N}} | \geq 2^{\log n} $$ or $$ c(1+\log d) = \omega (1), $$ which is a contradiction because we assumed that $c,d$ were constants.
If you allow a variable size alphabet for the position messages $p$ (or $d = \omega(1)$), then the question becomes algorithmically meaningless. Likewise, you may try to doing something clever like instead defining $\mathcal{P} \subset 2^{\{0,1,...,d-1\}}$, but a similar proof will again work.
Edit @ Jul 22 2022
Since the original question had an easy answer let us consider the following more difficult generalization of the question.
Suppose we allow the messages $p,$ $v$, and the encoding $\mathcal{E}$ to be longer. Then what is the lower bound on the $(p,v)$ messages?
Here is simpler pure information-theoretic proof. Sometimes it is easier to prove something by allowing a more powerful computational model and showing that even with this extra power you can't do better.
Here I will show you that no matter what set of questions you may ask (i.e., the $p$ messages can be replaced with arbitrary boolean functions), I will still always need at least $\Omega(n )$ many bits.
Theorem Any set of binary sequences that encode the subsets $\mathcal{S} \subset \mathcal{N}$ as position/value messages must have a minimum of $\Omega( n)$ many bits. Furthermore, this remains true if you replace the $p$ messages with arbitrary boolean functions.
(Proof) Suppose that $d,c$ is the number of positions/values that are used in a scheme. Consider the following decision tree. The root is labeled $r_{0,0} := \mathcal{S}$ and the children of the root are labeled $r_{1,(p_0,v_0)} := \{ x \in \mathcal{N}\ \mid \ \mathcal{E}(x)_{p_0}=v_0 \}$ and more generally the children of $r_{i,(p_i,v_i)}$ at layer $i+1$ are labeled $r_{i+1,(p_{i+1},v_{i+1})}:= \{ x \in r_{i,(p_i,v_i)} \ | \ \mathcal{E}(x)_{p_{i+1}}=v_{i+1}\} $. This forms a decision tree in an alphabet with at most $$2d \geq |\{(p_i,v_i) \in [d] \times [2] \mid (p_i,v_i) \in (p,v) \in \mathcal{P} \times \mathcal{V}\}|$$ many branches at any node. A classical information-theoretic argument (see Cover and Thomas) gives us that any such decision tree that can partition the power set must have at least $\Omega(2^n)=\Omega(|2^\mathcal{N}|)$ many nodes and thus at least $c = \log_{2d}(2^n)$ depth. However, the position messages $p$ require at least $\Omega(\log(d))$ amount of bits to encode. Thus the maximum message length, $$l = \max\{|(p,v)|\ \mid \ (p,v) \in \mathcal{P} \times \mathcal{V} \}$$, satisfies $$ l = \Omega(c\log(d)) = \Omega(\log_{2d}(2^n)\log(d)) = \Omega(n). $$ QED
-
1$\begingroup$ thank you pedro for your proof, which I appreciate. If I seek say a coding scheme of length polylog(N) and O(log n) length message or even $O(n^a)$ length with $a<1$, can we design such codes? $\endgroup$– lchenJul 21, 2022 at 10:14
-
$\begingroup$ Hey Ichen, thanks for the positive feedback! It is funny that you ask because I was going to add a comment about this but I didn't want to make the answer too long. If you notice in the proof I said that $\mathcal{E}: \mathcal{N} \rightarrow \{0,1\}^{\omega(1)}$ so that the proof actually does not depend on the length of the coding scheme! This surprised me while I was working on it. In particular, the contradiction inequality is $2^{c(1+\log d)} \geq |\mathcal{P} \times \mathcal{V}| \geq |2^{\mathcal{N}} | \geq 2^{\log n}$ which does not depend on the length of the coding scheme! Cool huh? $\endgroup$ Jul 21, 2022 at 14:35
-
$\begingroup$ @Ichen I believe I answered your more general question. You will always need $\omega(n)$ many bits for any scheme. Please take a look at the edited answer. Best wishes! $\endgroup$ Jul 22, 2022 at 23:58
-
$\begingroup$ @Ichen I actually realized that the proof proves something far stronger; you can replace the $p$ messages with any boolean functions $p'$ and the proof still works. It is an information-theoretic lower bound that follows directly from combinatorics/counting nodes on a decision tree. Best of luck! $\endgroup$ Jul 23, 2022 at 15:44