{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,26]],"date-time":"2026-08-26T16:07:19Z","timestamp":1787760439526,"version":"build-2784847793"},"reference-count":37,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2021,2,16]],"date-time":"2021-02-16T00:00:00Z","timestamp":1613433600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-18-16518, CCF-18-16546"],"award-info":[{"award-number":["CCF-18-16518, CCF-18-16546"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information"],"abstract":"<jats:p>Computer-aided methods, based on the entropic linear program framework, have been shown to be effective in assisting the study of information theoretic fundamental limits of information systems. One key element that significantly impacts their computation efficiency and applicability is the reduction of variables, based on problem-specific symmetry and dependence relations. In this work, we propose using the disjoint-set data structure to algorithmically identify the reduction mapping, instead of relying on exhaustive enumeration in the equivalence classification. Based on this reduced linear program, we consider four techniques to investigate the fundamental limits of information systems: (1) computing an outer bound for a given linear combination of information measures and providing the values of information measures at the optimal solution; (2) efficiently computing a polytope tradeoff outer bound between two information quantities; (3) producing a proof (as a weighted sum of known information inequalities) for a computed outer bound; and (4) providing the range for information quantities between which the optimal value does not change, i.e., sensitivity analysis. A toolbox, with an efficient JSON format input frontend, and either Gurobi or Cplex as the linear program solving engine, is implemented and open-sourced.<\/jats:p>","DOI":"10.3390\/info12020082","type":"journal-article","created":{"date-parts":[[2021,2,16]],"date-time":"2021-02-16T04:23:10Z","timestamp":1613449390000},"page":"82","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Computational Techniques for Investigating Information Theoretic Limits of Information Systems"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8752-6141","authenticated-orcid":false,"given":"Chao","family":"Tian","sequence":"first","affiliation":[{"name":"Department of Electrical and Computer Engineering, Texas A&amp;M University, College Station, TX 77843, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9841-6076","authenticated-orcid":false,"given":"James S.","family":"Plank","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering and Computer Science, University of Tennessee, Knoxville, TN 37996, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Brent","family":"Hurst","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering and Computer Science, University of Tennessee, Knoxville, TN 37996, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8855-2031","authenticated-orcid":false,"given":"Ruida","family":"Zhou","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, Texas A&amp;M University, College Station, TX 77843, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2021,2,16]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1924","DOI":"10.1109\/18.641556","article-title":"A framework for linear information inequalities","volume":"43","author":"Yeung","year":"1997","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"967","DOI":"10.1109\/JSAC.2014.140516","article-title":"Characterizing the rate region of the (4, 3, 3) exact-repair regenerating codes","volume":"32","author":"Tian","year":"2014","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"4833","DOI":"10.1109\/TIT.2016.2576467","article-title":"Multilevel diversity coding with regeneration","volume":"62","author":"Tian","year":"2016","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Tian, C. (2018). Symmetry, outer bounds, and code constructions: A computer-aided investigation on the fundamental limits of caching. Entropy, 20.","DOI":"10.3390\/e20080603"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1548","DOI":"10.1109\/TIT.2018.2794543","article-title":"Caching and delivery via interference elimination","volume":"64","author":"Tian","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Tian, C., Sun, H., and Chen, J. (2018, January 17\u201322). A Shannon-theoretic approach to the storage-retrieval tradeoff in PIR systems. Proceedings of the 2018 IEEE International Symposium on Information Theory (ISIT), Vail, CO, USA.","DOI":"10.1109\/ISIT.2018.8437874"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"7539","DOI":"10.1109\/TIT.2020.3015818","article-title":"On the storage cost of private information retrieval","volume":"66","author":"Tian","year":"2020","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1145\/364099.364331","article-title":"An improved equivalence algorithm","volume":"7","author":"Galler","year":"1964","journal-title":"Commun. ACM"},{"key":"ref_9","unstructured":"IBM (2021, February 15). IBM ILOG CPLEX Optimizer. Available online: https:\/\/www.ibm.com\/analytics\/cplex-optimizer."},{"key":"ref_10","unstructured":"Gurobi (2021, February 15). Gurobi Optimizer. Available online: https:\/\/www.gurobi.com\/."},{"key":"ref_11","unstructured":"(2021, February 15). An Open-Source Toolbox for Computer-Aided Investigation on the Fundamental Limits of Information Systems. Available online: https:\/\/github.com\/ct2641\/CAI."},{"key":"ref_12","unstructured":"(2020, December 15). Information Theoretic Inequality Prover (ITIP). Available online: http:\/\/user-www.ie.cuhk.edu.hk\/~ITIP\/."},{"key":"ref_13","unstructured":"(2020, December 15). Xitip: Information Theoretic Inequalities Prover. Available online: http:\/\/xitip.epfl.ch\/."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1996","DOI":"10.1109\/TIT.2002.1013139","article-title":"Information-theoretic characterizations of conditional mutual independence and Markov random fields","volume":"48","author":"Yeung","year":"2002","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Dougherty, R., Freiling, C., and Zeger, K. (2006, January 9\u201314). Six new non-Shannon information inequalities. Proceedings of the 2006 IEEE International Symposium on Information Theory (ISIT), Seattle, WA, USA.","DOI":"10.1109\/ISIT.2006.261840"},{"key":"ref_16","unstructured":"Dougherty, R., Freiling, C., and Zeger, K. (2011). Non-Shannon information inequalities in four random variables. arXiv."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1109\/TIT.2016.2628791","article-title":"Multilevel diversity coding systems: Rate regions, codes, computation, & forbidden minors","volume":"63","author":"Li","year":"2016","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"5522","DOI":"10.1109\/TIT.2020.2982642","article-title":"Proving and disproving information inequalities: Theory and scalable algorithms","volume":"66","author":"Ho","year":"2020","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"4041","DOI":"10.1109\/TIT.2019.2900669","article-title":"Minimal characterization of Shannon-type inequalities under functional dependence and full conditional independence structures","volume":"65","author":"Chan","year":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"2396","DOI":"10.1109\/TCOMM.2017.2757474","article-title":"On the symmetry reduction of information inequalities","volume":"66","author":"Zhang","year":"2018","journal-title":"IEEE Trans. Commun."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"7283","DOI":"10.1109\/TIT.2017.2745620","article-title":"On multi-source networks: Enumeration, rate region computation, and hierarchy","volume":"63","author":"Li","year":"2017","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Apte, J., and Walsh, J.M. (2015, January 22\u201324). Exploiting symmetry in computing polyhedral bounds on network coding rate regions. Proceedings of the 2015 International symposium on network coding (NetCod), Sydney, Australia.","DOI":"10.1109\/NETCOD.2015.7176793"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Li, C., Apte, J., Walsh, J.M., and Weber, S. (2013, January 7\u20139). A new computational approach for determining rate regions and optimal codes for coded networks. Proceedings of the 2013 International Symposium on Network Coding (NetCod), Calgary, AB, Canada.","DOI":"10.1109\/NetCod.2013.6570825"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Apte, J., Li, C., and Walsh, J.M. (July, January 29). Algorithms for computing network coding rate regions via single element extensions of matroids. Proceedings of the 2014 IEEE International Symposium on Information Theory (ISIT), Honolulu, HI, USA.","DOI":"10.1109\/ISIT.2014.6875245"},{"key":"ref_25","first-page":"25","article-title":"Fourier-Motzkin elimination software for information theoretic inequalities","volume":"65","author":"Gattegno","year":"2015","journal-title":"IEEE Inf. Theory Newsl."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"G\u00fcrp\u0131nar, E., and Romashchenko, A. (2019, January 7\u201312). How to use undiscovered information inequalities: Direct applications of the copy lemma. Proceedings of the 2019 IEEE International Symposium on Information Theory (ISIT), Paris, France.","DOI":"10.1109\/ISIT.2019.8849309"},{"key":"ref_27","unstructured":"Cover, T.M., and Thomas, J.A. (1991). Elements of Information Theory, Wiley. [1st ed.]."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Yeung, R. (2002). A First Course in Information Theory, Kluwer Academic Publishers.","DOI":"10.1007\/978-1-4419-8608-5"},{"key":"ref_29","unstructured":"Yeung, R.W. (2008). Information Theory and Network Coding, Springer Science & Business Media."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1982","DOI":"10.1109\/18.641561","article-title":"A non-Shannon-type conditional inequality of information quantities","volume":"43","author":"Zhang","year":"1997","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Matus, F. (2007, January 24\u201329). Infinitely many information inequalities. Proceedings of the 2007 IEEE International Symposium on Information Theory (ISIT), Nice, France.","DOI":"10.1109\/ISIT.2007.4557201"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"2745","DOI":"10.1109\/TIT.2005.851744","article-title":"Insufficiency of linear coding in network information flow","volume":"51","author":"Dougherty","year":"2005","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"1949","DOI":"10.1109\/TIT.2007.896862","article-title":"Networks, matroids, and non-Shannon information inequalities","volume":"53","author":"Dougherty","year":"2007","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"4539","DOI":"10.1109\/TIT.2010.2054295","article-title":"Network coding for distributed storage systems","volume":"56","author":"Dimakis","year":"2010","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"476","DOI":"10.1109\/JPROC.2010.2096170","article-title":"A survey on network codes for distributed storage","volume":"99","author":"Dimakis","year":"2011","journal-title":"Proc. IEEE"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"2856","DOI":"10.1109\/TIT.2014.2306938","article-title":"Fundamental limits of caching","volume":"60","author":"Niesen","year":"2014","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_37","unstructured":"Donald, B.R., Kapur, D., and Mundy, J.L. (1992). Symbolic and Numerical Computation for Artificial Intelligence, Academic Press. Chapter 4 Quantifier Elimination for Conjunctions of Linear Constraints via a Convex Hull Algorithm."}],"container-title":["Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2078-2489\/12\/2\/82\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:24:40Z","timestamp":1760160280000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2078-2489\/12\/2\/82"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,16]]},"references-count":37,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2021,2]]}},"alternative-id":["info12020082"],"URL":"https:\/\/doi.org\/10.3390\/info12020082","relation":{},"ISSN":["2078-2489"],"issn-type":[{"value":"2078-2489","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,16]]}}}