4
$\begingroup$

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.

$\endgroup$
2
  • 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$ Jul 17 at 5:12
  • $\begingroup$ What about allowing ${\cal O}(\log N)$ message length $\endgroup$
    – lchen
    Jul 17 at 5:43

1 Answer 1

1
$\begingroup$

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

$\endgroup$
4
  • 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$
    – lchen
    Jul 21 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 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 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 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.