{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:59:31Z","timestamp":1760144371541,"version":"build-2065373602"},"reference-count":19,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2024,4,16]],"date-time":"2024-04-16T00:00:00Z","timestamp":1713225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Cominlabs excellence laboratory with the French National Research Agency\u2019s funding","award":["ANR-10-LABX-07-01"],"award-info":[{"award-number":["ANR-10-LABX-07-01"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>We investigate the zero-error coding for computing problems with encoder side information. An encoder provides access to a source X and is furnished with side information g(Y). It communicates with a decoder that possesses side information Y and aims to retrieve f(X,Y) with zero probability of error, where f and g are assumed to be deterministic functions. In previous work, we determined a condition that yields an analytic expression for the optimal rate R*(g); in particular, it covers the case where PX,Y is full support. In this article, we review this result and study the side information design problem, which consists of finding the best trade-offs between the quality of the encoder\u2019s side information g(Y) and R*(g). We construct two greedy algorithms that give an achievable set of points in the side information design problem, based on partition refining and coarsening. One of them runs in polynomial time.<\/jats:p>","DOI":"10.3390\/e26040338","type":"journal-article","created":{"date-parts":[[2024,4,16]],"date-time":"2024-04-16T04:21:59Z","timestamp":1713241319000},"page":"338","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Side Information Design in Zero-Error Coding for Computing"],"prefix":"10.3390","volume":"26","author":[{"given":"Nicolas","family":"Charpenay","sequence":"first","affiliation":[{"name":"Univ. Rennes, CNRS, IRMAR UMR 6625, F-35000 Rennes, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6806-8592","authenticated-orcid":false,"given":"Ma\u00ebl","family":"Le Treust","sequence":"additional","affiliation":[{"name":"Univ. Rennes, CNRS, Inria, IRISA UMR 6074, F-35000 Rennes, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6352-8166","authenticated-orcid":false,"given":"Aline","family":"Roumy","sequence":"additional","affiliation":[{"name":"INRIA Rennes, Campus de Beaulieu, F-35000 Rennes cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2024,4,16]]},"reference":[{"unstructured":"Orlitsky, A., and Roche, J.R. (1995, January 23\u201325). Coding for computing. Proceedings of the IEEE 36th Annual Foundations of Computer Science, Milwaukee, WI, USA.","key":"ref_1"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"8680","DOI":"10.1109\/TIP.2020.3016485","article-title":"Video coding for machines: A paradigm of collaborative compression and intelligent analytics","volume":"29","author":"Duan","year":"2020","journal-title":"IEEE Trans. Image Process."},{"unstructured":"Gao, W., Liu, S., Xu, X., Rafie, M., Zhang, Y., and Curcio, I. (2021). Recent standard development activities on video coding for machines. arXiv.","key":"ref_3"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1109\/TIT.1982.1056560","article-title":"Wyner-ziv theory for a general function of the correlated sources (corresp.)","volume":"28","author":"Yamamoto","year":"1982","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"3435","DOI":"10.1109\/TIT.2014.2303802","article-title":"Distributed computing and the graph entropy region","volume":"60","author":"Shayevitz","year":"2014","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1495","DOI":"10.1109\/TIT.2010.2103852","article-title":"Distributed source coding using abelian group codes: A new achievable rate-distortion region","volume":"57","author":"Krithivasan","year":"2011","journal-title":"IEEE Trans. Inf. Theory"},{"doi-asserted-by":"crossref","unstructured":"Basu, S., Seo, D., and Varshney, L.R. (2020, January 21\u201326). Hypergraph-based Coding Schemes for Two Source Coding Problems under Maximal Distortion. Proceedings of the IEEE International Symposium on Information Theory (ISIT), Los Angeles, CA, USA.","key":"ref_7","DOI":"10.1109\/ISIT44484.2020.9174396"},{"doi-asserted-by":"crossref","unstructured":"Malak, D., and M\u00e9dard, M. (2020, January 26\u201329). Hyper Binning for Distributed Function Coding. Proceedings of the 2020 IEEE 21st International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), Atlanta, GA, USA.","key":"ref_8","DOI":"10.1109\/SPAWC48557.2020.9154232"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"5387","DOI":"10.1109\/TIT.2014.2332464","article-title":"On network functional compression","volume":"60","author":"Feizi","year":"2014","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"7135","DOI":"10.1109\/TIT.2016.2530398","article-title":"Distributed function computation over a rooted directed tree","volume":"62","author":"Sefidgaran","year":"2016","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"902","DOI":"10.1109\/TIT.2018.2884490","article-title":"Function Computation Through a Bidirectional Relay","volume":"65","author":"Ravi","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"3790","DOI":"10.1109\/TIT.2019.2893107","article-title":"Improved upper bound on the network function computing capacity","volume":"65","author":"Guang","year":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"doi-asserted-by":"crossref","unstructured":"Charpenay, N., Le Treust, M., and Roumy, A. (2023, January 23\u201328). Optimal Zero-Error Coding for Computing under Pairwise Shared Side Information. Proceedings of the 2023 IEEE Information Theory Workshop (ITW), Saint-Malo, France.","key":"ref_13","DOI":"10.1109\/ITW55543.2023.10161637"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1329","DOI":"10.1109\/18.532875","article-title":"Source coding and graph entropies","volume":"42","author":"Alon","year":"1996","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"592","DOI":"10.1109\/TIT.1976.1055607","article-title":"The zero-error side information problem and chromatic numbers (corresp.)","volume":"22","author":"Witsenhausen","year":"1976","journal-title":"IEEE Trans. Inf. Theory"},{"unstructured":"K\u00f6rner, J. (1973, January 19\u201325). 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.","key":"ref_16"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"2537","DOI":"10.1109\/TIT.2009.2018182","article-title":"On complementary graph entropy","volume":"55","author":"Tuncel","year":"2009","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/BF02122693","article-title":"Entropy splitting for antiblocking corners and perfect graphs","volume":"10","author":"Marton","year":"1990","journal-title":"Combinatorica"},{"doi-asserted-by":"crossref","unstructured":"Csisz\u00e1r, I., and K\u00f6rner, J. (2011). Information Theory: Coding Theorems for Discrete Memoryless Systems, Cambridge University Press.","key":"ref_19","DOI":"10.1017\/CBO9780511921889"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/26\/4\/338\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T14:28:27Z","timestamp":1760106507000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/26\/4\/338"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,16]]},"references-count":19,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2024,4]]}},"alternative-id":["e26040338"],"URL":"https:\/\/doi.org\/10.3390\/e26040338","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2024,4,16]]}}}