# 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.

• 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.