# Deterministic one way communication complexity for message with arbitrary length

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.

• This should help en.wikipedia.org/wiki/Variable-length_quantity Commented Apr 10, 2021 at 17:45
• 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 ? Commented Apr 11, 2021 at 0:45
• What is a "one-bit communication channel"?
– usul
Commented Apr 11, 2021 at 15:07
• @usul Alice can send one bit at a time. Commented Apr 11, 2021 at 18:25
• 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
Commented Apr 12, 2021 at 14:51