{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T05:34:07Z","timestamp":1764912847813,"version":"3.46.0"},"reference-count":27,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T00:00:00Z","timestamp":1764720000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Key Research and Development Program of China","award":["2023YFA1009604"],"award-info":[{"award-number":["2023YFA1009604"]}]},{"DOI":"10.13039\/501100001809","name":"Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62171238, 62461160306"],"award-info":[{"award-number":["62171238, 62461160306"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"the Fundamental Research Funds for the Central Universities","award":["050-63253087"],"award-info":[{"award-number":["050-63253087"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>The problem of multi-function computation over a directed acyclic network is investigated in this paper. In such a network, a sink node is required to compute with zero error multiple vector-linear functions, where each vector-linear function has distinct inputs generated by multiple source nodes. The computing rate tuple of an admissible code is defined as a tuple consisting of the average number of zero-error computations for each vector-linear function when the network is used once jointly. From the information theoretic point of view, we are interested in characterizing the rate region, which is defined as the closed set of all achievable computing rate tuples. In particular, when the sink node is required to compute a single vector-linear function, the network multi-function computation problem degenerates to the network function computation problem. We prove an outer bound on the rate region by developing the approach of the cut-set strong partition. We also illustrate that the obtained outer bound is tight for a typical model of computing two vector-linear functions over the diamond network. Furthermore, we establish the relationship between the network multi-function computation rate region and the network function computation rate region. Also, we show that the best known outer bound on the rate region for computing an arbitrary vector-linear function over an arbitrary network is a straightforward consequence of our outer bound.<\/jats:p>","DOI":"10.3390\/e27121225","type":"journal-article","created":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T15:02:48Z","timestamp":1764774168000},"page":"1225","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Multi-Function Computation over a Directed Acyclic Network"],"prefix":"10.3390","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-0766-7605","authenticated-orcid":false,"given":"Xiufang","family":"Sun","sequence":"first","affiliation":[{"name":"School of Mathematical Sciences and LPMC, Nankai University, Tianjin 300071, China"}]},{"given":"Ruze","family":"Zhang","sequence":"additional","affiliation":[{"name":"Institute of Network Coding, The Chinese University of Hong Kong, Hong Kong SAR, China"}]},{"given":"Dan","family":"Li","sequence":"additional","affiliation":[{"name":"School of Science, Tianjin University of Technology, Tianjin 300384, China"}]},{"given":"Xuan","family":"Guang","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences and LPMC, Nankai University, Tianjin 300071, China"}]}],"member":"1968","published-online":{"date-parts":[[2025,12,3]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1015","DOI":"10.1109\/TIT.2010.2095070","article-title":"Network coding for computing: Cut-set bounds","volume":"57","author":"Appuswamy","year":"2011","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"6454","DOI":"10.1109\/TIT.2018.2827405","article-title":"Comments on cut-set bounds on network function computation","volume":"64","author":"Huang","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1109\/TIT.2013.2283075","article-title":"Computing linear functions by linear coding over networks","volume":"60","author":"Appuswamy","year":"2014","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_4","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"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"5741","DOI":"10.1109\/TIT.2013.2252052","article-title":"Linear codes, target function classes, and network computing capacity","volume":"59","author":"Appuswamy","year":"2013","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1109\/JSAC.2013.130404","article-title":"Communicating the sum of sources over a network","volume":"31","author":"Ramamoorthy","year":"2013","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1109\/TIT.2011.2169532","article-title":"On network coding for sum-networks","volume":"58","author":"Rai","year":"2012","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"2144","DOI":"10.1109\/LCOMM.2013.101413.131605","article-title":"Sum-networks: Min-cut = 2 does not guarantee solvability","volume":"17","author":"Rai","year":"2013","journal-title":"IEEE Commun. Lett."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"3461","DOI":"10.1109\/TIT.2017.2765661","article-title":"Sum-networks from incidence structures: Construction and capacity analysis","volume":"64","author":"Tripathy","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"3407","DOI":"10.1109\/TIT.2012.2188883","article-title":"Optimal function computation in directed and undirected graphs","volume":"58","author":"Kowshik","year":"2012","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1109\/JSAC.2005.843543","article-title":"Computing and communicating functions over sensor networks","volume":"23","author":"Giridhar","year":"2005","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1519","DOI":"10.1109\/LCOMM.2022.3170974","article-title":"Computing vector-linear functions on diamond network","volume":"26","author":"Li","year":"2022","journal-title":"IEEE Commun. Lett."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1109\/JSAIT.2024.3453273","article-title":"Computation of binary arithmetic sum over an asymmetric diamond network","volume":"5","author":"Zhang","year":"2024","journal-title":"IEEE J. Sel. Areas Inf. Theory"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1111","DOI":"10.1109\/TIT.2023.3319976","article-title":"Zero-error distributed compression of binary arithmetic sum","volume":"70","author":"Guang","year":"2024","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Tripathy, A., and Ramamoorthy, A. (2016, January 10\u201315). On computation rates for arithmetic sum. Proceedings of the 2016 the IEEE International Symposium on Information Theory (ISIT), Barcelona, Spain.","DOI":"10.1109\/ISIT.2016.7541720"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Tripathy, A., and Ramamoorthy, A. (2018, January 25\u201329). Zero-error function computation on a directed acyclic network. Proceedings of the 2018 IEEE Information Theory Workshop (ITW), Guangzhou, China.","DOI":"10.1109\/ITW.2018.8613467"},{"key":"ref_17","unstructured":"Feizi, S., and M\u00e9dard, M. (December, January 30). Multi-functional compression with side information. Proceedings of the IEEE Global Communications Conference, Honolulu, HI, USA."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"702","DOI":"10.1109\/JSAC.2013.130408","article-title":"Multi-session function computation and multicasting in undirected graphs","volume":"31","author":"Kannan","year":"2013","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"6826","DOI":"10.1109\/TIT.2022.3182416","article-title":"Private remote sources for secure multi-function computation","volume":"68","author":"Bloch","year":"2022","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Kim, W., Kruglik, S., and Kiah, H.M. (2023, January 23\u201328). Coded computation of multiple functions. Proceedings of the IEEE Information Theory Workshop, Sundsvall, Sweden.","DOI":"10.1109\/ITW55543.2023.10161651"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"8009","DOI":"10.1109\/TIFS.2024.3450288","article-title":"Verifiable coded computation of multiple functions","volume":"19","author":"Kim","year":"2024","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Malak, D., Deylam Salehi, M., Serbetci, B., and Elia, P. (2024). Multi-server multi-function distributed computation. Entropy, 26.","DOI":"10.3390\/e26060448"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Huang, L., Feng, X., Zhang, L., Qian, L., and Wu, Y. (2019). Multi-server multi-user multi-task computation offloading for mobile edge computing networks. Sensors, 19.","DOI":"10.3390\/s19061446"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1109\/LSP.2020.3044259","article-title":"Multi-function radar signal sorting based on complex network","volume":"28","author":"Chi","year":"2021","journal-title":"IEEE Signal Process. Lett."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1093\/comjnl\/bxt120","article-title":"Generative neural networks for multi-task life-long learning","volume":"57","author":"Reeder","year":"2014","journal-title":"Comput. J."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Iwai, H., and Kobayashi, I. (2023, January 25\u201326). A study on developmental artificial neural networks that integrate multiple functions using variational autoencoder. Proceedings of the International Conference on Soft Computing and Machine Intelligence, Mexico City, Mexico.","DOI":"10.1109\/ISCMI59957.2023.10458661"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Malak, D., Salehi, M.R.D., Serbetci, B., and Elia, P. (2024, January 24\u201327). Multi-functional distributed computing. Proceedings of the 60th Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, USA.","DOI":"10.1109\/Allerton63246.2024.10735279"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/27\/12\/1225\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T05:28:14Z","timestamp":1764912494000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/27\/12\/1225"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,3]]},"references-count":27,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2025,12]]}},"alternative-id":["e27121225"],"URL":"https:\/\/doi.org\/10.3390\/e27121225","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2025,12,3]]}}}