{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T18:09:46Z","timestamp":1771610986345,"version":"3.50.1"},"reference-count":27,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2021,11,15]],"date-time":"2021-11-15T00:00:00Z","timestamp":1636934400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["ERC grant no. 639573"],"award-info":[{"award-number":["ERC grant no. 639573"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["ISF grant no. 1495\/18"],"award-info":[{"award-number":["ISF grant no. 1495\/18"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JSPS grant no. 21K13830"],"award-info":[{"award-number":["JSPS grant no. 21K13830"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>We study the problem of communicating over a discrete memoryless two-way channel using non-adaptive schemes, under a zero probability of error criterion. We derive single-letter inner and outer bounds for the zero-error capacity region, based on random coding, linear programming, linear codes, and the asymptotic spectrum of graphs. Among others, we provide a single-letter outer bound based on a combination of Shannon\u2019s vanishing-error capacity region and a two-way analogue of the linear programming bound for point-to-point channels, which, in contrast to the one-way case, is generally better than both. Moreover, we establish an outer bound for the zero-error capacity region of a two-way channel via the asymptotic spectrum of graphs, and show that this bound can be achieved in certain cases.<\/jats:p>","DOI":"10.3390\/e23111518","type":"journal-article","created":{"date-parts":[[2021,11,15]],"date-time":"2021-11-15T08:19:20Z","timestamp":1636964360000},"page":"1518","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On the Non-Adaptive Zero-Error Capacity of the Discrete Memoryless Two-Way Channel"],"prefix":"10.3390","volume":"23","author":[{"given":"Yujie","family":"Gu","sequence":"first","affiliation":[{"name":"Faculty of Information Science and Electrical Engineering, Kyushu University, Fukuoka 819-0395, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ofer","family":"Shayevitz","sequence":"additional","affiliation":[{"name":"Department of EE\u2014Systems, Tel Aviv University, Tel Aviv 69978, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,11,15]]},"reference":[{"key":"ref_1","unstructured":"Shannon, C.E. (July, January 20). Two-way communication channels. Proceedings of the 4th Berkeley Symposium Mathematics, Statistics and Probability, Oakland, CA, USA."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1109\/TIT.1956.1056798","article-title":"The zero error capacity of a noisy channel","volume":"2","author":"Shannon","year":"1956","journal-title":"IRE Trans. Inf. Theory"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1109\/TIT.1984.1056847","article-title":"A general coding scheme for the two-way channel","volume":"30","author":"Han","year":"1984","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1109\/18.42175","article-title":"Dependence balance bounds for single-output two-way channels","volume":"35","author":"Hekstra","year":"1989","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1109\/TIT.1986.1057192","article-title":"New outer bounds to capacity regions of two-way channels","volume":"32","author":"Zhang","year":"1986","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"6290","DOI":"10.1109\/TIT.2019.2919295","article-title":"Capacity of two-way channels with symmetry properties","volume":"65","author":"Weng","year":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Weng, J., Song, L., Alajaji, F., and Linder, T. (2018, January 17\u201322). Sufficient conditions for the tightness of Shannon\u2019s capacity bounds for two-way channels. Proceedings of the 2018 IEEE International Symposium on Information Theory (ISIT), Vail, CO, USA.","DOI":"10.1109\/ISIT.2018.8437799"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Sabag, O., and Permuter, H.H. (2018, January 2\u20135). An achievable rate region for the two-way channel with common output. Proceedings of the 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton), Monticello, IL, USA.","DOI":"10.1109\/ALLERTON.2018.8635930"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1109\/TIT.1982.1056441","article-title":"The binary multiplying channel\u2014A coding scheme that operates beyond Shannon\u2019s inner bound region","volume":"28","author":"Schalkwijk","year":"1982","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1109\/TIT.1983.1056661","article-title":"On an extension of an achievable rate region for the binary multiplying channel","volume":"29","author":"Schalkwijk","year":"1983","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1109\/TIT.1979.1056027","article-title":"On some problems of Lov\u00e1sz concerning the Shannon capacity of a graph","volume":"25","author":"Haemers","year":"1979","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","article-title":"On the Shannon capacity of a graph","volume":"25","year":"1979","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0195-6698(95)90031-4","article-title":"Cancellative pairs of families of sets","volume":"16","author":"Holzman","year":"1995","journal-title":"Eur. J. Combin."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"2","DOI":"10.37236\/7210","article-title":"A new upper bound for cancellative pairs","volume":"25","author":"Janzer","year":"2018","journal-title":"Electron. J. Combin."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1043","DOI":"10.1109\/18.841182","article-title":"New rate pairs in the zero-error capacity region of the binary multiplying channel without feedback","volume":"46","author":"Tolhuizen","year":"2000","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Gu, Y., and Shayevitz, O. (2019, January 7\u201312). On the non-adaptive zero-error capacity of the discrete memoryless two-way channel. Proceedings of the 2019 IEEE International Symposium on Information Theory (ISIT), Paris, France.","DOI":"10.1109\/ISIT.2019.8849699"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1173","DOI":"10.1007\/s00493-019-3992-5","article-title":"The asymptotic spectrum of graphs and the Shannon capacity","volume":"39","author":"Zuiddam","year":"2019","journal-title":"Combinatorica"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"7330","DOI":"10.1109\/TIT.2014.2349502","article-title":"Bounds on entanglement-assisted source-channel coding via the Lov\u00e1sz theta number and its variants","volume":"60","author":"Cubitt","year":"2014","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_19","unstructured":"Blasiak, A. (2013). A Graph-Theoretic Approach to Network Coding. [Ph.D. Thesis, Cornell University]."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"3340","DOI":"10.1109\/TIT.2018.2889108","article-title":"On a fractional version of Haemers\u2019 bound","volume":"65","author":"Bukh","year":"2019","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/PL00009824","article-title":"The Shannon capacity of a union","volume":"18","author":"Alon","year":"1998","journal-title":"Combinatorica"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/BF00535895","article-title":"Channels with arbitrarily varying channel probability functions in the presence of noiseless feedback","volume":"25","author":"Ahlswede","year":"1973","journal-title":"Z. Wahrscheinlichkeitstheorie Verwandte Geb."},{"key":"ref_23","unstructured":"Csisz\u00e1r, I., and K\u00f6rner, J. (1981). Information Theory: Coding Theorems for Discrete Memoryless Systems, Cambridge University Press."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/BF00533715","article-title":"On the capacity of the arbitrarily varying channel for maximum probability of error","volume":"57","year":"1981","journal-title":"Z. Wahrscheinlichkeitstheorie Verwandte Geb."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Vrana, P. (2021). Probabilistic refinement of the asymptotic spectrum of graphs. Combinatorica.","DOI":"10.1007\/s00493-020-4324-5"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1006\/jctb.1993.1015","article-title":"On the Shannon capacity of probabilistic graphs","volume":"57","author":"Marton","year":"1993","journal-title":"J. Comb. Theory Ser. B"},{"key":"ref_27","unstructured":"K\u00f6rner, J. (1973, January 1). Coding of an information source having ambiguous alphabet and the entropy of graphs. Proceedings of the 6th Prague Conference on Information Theory, Prague, Czech Republic."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/11\/1518\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:30:29Z","timestamp":1760167829000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/11\/1518"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,15]]},"references-count":27,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2021,11]]}},"alternative-id":["e23111518"],"URL":"https:\/\/doi.org\/10.3390\/e23111518","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,15]]}}}