1
$\begingroup$

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.

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

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.