<p>Let Alice have a binary string of length <span class="math-container">$n$</span> that it wants to send to Bob along a one-bit communication channel. However, Bob does not know the length of the message.</p>
<p>I have been looking into communication complexity material but everything that I found assumes that the receiver (i.e. Bob) knows the length of <span class="math-container">$n$</span> in advance.</p>
<p>I would really appreciate a pointer to martial that I should be looking into.</p>
<p>Thank you in advance.</p>

CC BY-SA 4.0
2021-04-10T17:45:30.463Z
This should help https://en.wikipedia.org/wiki/Variable-length_quantity
notautogenerated
CC BY-SA 4.0
2021-04-11T00:45:26.377Z
Thank you for your response. Do you know if this algorithm is optimal (I looked at the references in the wiki page but no luck) or is there a lower bound result regarding this problem ?
Koko Nanahji
CC BY-SA 4.0
2021-04-11T15:07:11.207Z
What is a "one-bit communication channel"?
usul
CC BY-SA 4.0
2021-04-11T18:25:32.203Z
@usul Alice can send one bit at a time.
Koko Nanahji
CC BY-SA 4.0
2021-04-12T14:51:54.800Z
Can you explain what you're looking for in more detail? We can do $2n$ by interleaving the message with "stop bits" that are 1 if the message continues or 0 if the message has ended. We can't do better than $n$. I think we can achieve $n + 2\log(n) = n(1+o(1))$ by first sending the length of message interleaved with stop bits, then sending the message itself.
usul
CC BY-SA 4.0
2021-04-12T15:39:15.390Z
Oh, you might also be interested in prefix codes: https://en.wikipedia.org/wiki/Prefix_code
usul
CC BY-SA 4.0
2021-04-12T17:31:02.813Z
@usul Thank you for the suggestions. To be more specific, I am looking for an optimal algorithm (in terms of number of bits sent) that can be used to send an arbitrary sized message from Alice to Bob along a one-bit communication channel. 
The algorithms that you suggested are asymptotically optimal, but I am looking for an algorithm that sends the exact number number of bits required (i.e. without dropping the coefficients).
Meaning, I know that $n$ is a lower bound. But is there a better lower bound than $n$. If so, is there an algorithm that has a matching upper bound ?
Koko Nanahji
<it.information-theory><communication-complexity><complexity>
Deterministic one way communication complexity for message with arbitrary length
Koko Nanahji
# Deterministic one way communication complexity for message with arbitrary length

(Asked by: username_0 on 2021-04-10)

Let Alice have a binary string of length $n$ that it wants to send to Bob along a one-bit communication channel. However, Bob does not know the length of the message.

I have been looking into communication complexity material but everything that I found assumes that the receiver (i.e. Bob) knows the length of $n$ in advance.

I would really appreciate a pointer to martial that I should be looking into.

Thank you in advance.

**Tags:** it.information-theory, communication-complexity, complexity
> **Comments:**
> **username_1**: This should help https://en.wikipedia.org/wiki/Variable-length_quantity  
> **username_0**: Thank you for your response. Do you know if this algorithm is optimal (I looked at the references in the wiki page but no luck) or is there a lower bound result regarding this problem ?  
> **username_2**: What is a "one-bit communication channel"?  
> **username_0**: @usul Alice can send one bit at a time.  
> **username_2**: Can you explain what you're looking for in more detail? We can do $2n$ by interleaving the message with "stop bits" that are 1 if the message continues or 0 if the message has ended. We can't do better than $n$. I think we can achieve $n + 2\log(n) = n(1+o(1))$ by first sending the length of message interleaved with stop bits, then sending the message itself.  
> **username_2**: Oh, you might also be interested in prefix codes: https://en.wikipedia.org/wiki/Prefix_code  
> **username_0**: @usul Thank you for the suggestions. To be more specific, I am looking for an optimal algorithm (in terms of number of bits sent) that can be used to send an arbitrary sized message from Alice to Bob along a one-bit communication channel.  The algorithms that you suggested are asymptotically optimal, but I am looking for an algorithm that sends the exact number number of bits required (i.e. without dropping the coefficients). Meaning, I know that $n$ is a lower bound. But is there a better lower bound than $n$. If so, is there an algorithm that has a matching upper bound ?  

---

## 0 answers

