Symmetric capacity of the binary multiplying two-way channel
Two terminals hold independent messages $M_1, M_2$, each uniformly distributed. At each use $t = 1, \dots, N$ of the channel, terminal $i$ sends a bit $X_{i,t}$, which may be any function of $(M_i, Y_1, \dots, Y_{t-1})$, and both terminals receive $$Y_t = X_{1,t} X_{2,t}.$$ After $N$ uses each terminal estimates the other's message from its own message and $Y^N = (Y_1, \dots, Y_N)$. The symmetric capacity $C_{\mathrm{sym}}$ is the supremum of the rates $R$ for which both message sets can have at least $2^{NR}$ elements, along a sequence of block lengths tending to infinity, while the probability that either decoder errs tends to zero; rates are in bits per terminal per channel use. Shannon's inner and outer bounds for two-way channels give $0.6170 \le C_{\mathrm{sym}} \le 0.6942$ for this channel. Schalkwijk's adaptive coding schemes give $C_{\mathrm{sym}} \ge 0.6191$ (1982) and $C_{\mathrm{sym}} \ge 0.6306$ (1983), and the dependence balance bound of Hekstra and Willems gives $C_{\mathrm{sym}} \le 0.6463$ (1989).
Problem. Determine $C_{\mathrm{sym}}$.
Source: Shannon (1961), who introduced the binary multiplying channel as a two-way channel on which his inner and outer bounds differ; see El Gamal and Kim (2011), Chapter 17. Stated by AIM — Open Applied Problems as the symmetric capacity.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- IT — Information Theory
- Secondary
- PR
- Keywords
- AIM Open Applied Problems, channel capacity, interactive communication, two-way channels
References
@inproceedings{shannon1961,
author = {Shannon, C. E.},
title = {Two-way communication channels},
booktitle = {Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1},
publisher = {University of California Press},
address = {Berkeley, CA},
year = {1961},
pages = {611--644},
}
@incollection{elgamal2011twoway,
author = {El Gamal, Abbas and Kim, Young-Han},
title = {Interactive channel coding},
booktitle = {Network Information Theory},
publisher = {Cambridge University Press},
address = {Cambridge},
year = {2011},
pages = {427--458},
doi = {10.1017/CBO9781139030687.019},
}
@article{schalkwijk1982,
author = {Schalkwijk, J. P. M.},
title = {The binary multiplying channel---a coding scheme that operates beyond {S}hannon's inner bound region},
journal = {IEEE Trans. Inform. Theory},
volume = {28},
number = {1},
year = {1982},
pages = {107--110},
doi = {10.1109/TIT.1982.1056441},
}
@article{schalkwijk1983,
author = {Schalkwijk, J. P. M.},
title = {On an extension of an achievable rate region for the binary multiplying channel},
journal = {IEEE Trans. Inform. Theory},
volume = {29},
number = {3},
year = {1983},
pages = {445--448},
doi = {10.1109/TIT.1983.1056661},
}
@article{hekstra1989,
author = {Hekstra, Andries P. and Willems, Frans M. J.},
title = {Dependence balance bounds for single-output two-way channels},
journal = {IEEE Trans. Inform. Theory},
volume = {35},
number = {1},
year = {1989},
pages = {44--53},
doi = {10.1109/18.42175},
}
@misc{aim-binary-multiplying-two-way-capacity,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Symmetric capacity of the binary multiplying two-way channel}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/135-binary-multiplying-two-way-capacity.md},
note = {Entry 135 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00503, "Symmetric capacity of the binary multiplying two-way channel", clopen.solutions.