Adversarial binary interactive capacity conjecture without shared randomness

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Θ(ϵloglog1ϵ).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.

Sources & referencesView supporting material

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.