Adversarial binary interactive capacity conjecture without shared randomness

About 12 years old · traced to

Consider fully adversarial binary error channels without shared randomness, with noise rate ϵ→0\epsilon\to0. Let RR denote the interactive channel capacity, namely the maximal asymptotically achievable communication rate. Adversarial binary interactive capacity conjecture.

R=1−Θ(ϵlog⁡log⁡1ϵ).R=1-\Theta\left(\sqrt{\epsilon\log\log\frac{1}{\epsilon}}\right).

This conjecture concerns the fully adversarial binary setting without shared randomness; the source notes that the corresponding bound does not extend to larger alphabets.

References

Primary source

Bernhard Haeupler, “Interactive Channel Capacity Revisited”, arXiv:1408.1467 (2014).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.