标题： 对称性、外部界限和码构造：对缓存基本极限的计算机辅助研究 显示英文标题

标题： Symmetry, Outer Bounds, and Code Constructions: A Computer-Aided Investigation on the Fundamental Limits of Caching

摘要： 我们说明如何使用计算机辅助方法来研究缓存系统的根本限制，这些限制与信息论文献中通常看到的传统分析方法显著不同。 熵空间的线性规划（LP）外部界限作为这种方法的起点；然而，我们的工作远远超出了仅使用它来证明信息不等式。 我们首先识别并形式化了问题中的对称性结构，这使我们能够证明最优对称解的存在性。 然后使用对称性简化的线性规划来确定几个小案例中存储-传输速率权衡的边界，我们获得了紧致的外部界限集。 从这些计算数据中形成了关于最优权衡区域的一般假设，并随后进行了分析证明。 这导致了仅包含两个用户的系统最优权衡的完整表征，以及仅包含两个文件的系统的某些部分表征。 接下来，我们展示了通过仔细分析某些情况下外部界限的联合熵结构，可以反向工程出一种新颖的编码构造，最终导致一个通用的编码类。 最后，我们展示了可以通过以不同方式有策略地放松LP来计算外部界限，这可以用于计算探索该问题。 这使我们首先能够推导出对偶证明的一般特征，其次即使在看似不可能的计算规模下，也能计算更大问题案例的外部界限。 显示英文摘要

摘要： We illustrate how computer-aided methods can be used to investigate the fundamental limits of the caching systems, which are significantly different from the conventional analytical approach usually seen in the information theory literature. The linear programming (LP) outer bound of the entropy space serves as the starting point of this approach; however, our effort goes significantly beyond using it to prove information inequalities. We first identify and formalize the symmetry structure in the problem, which enables us to show the existence of optimal symmetric solutions. A symmetry-reduced linear program is then used to identify the boundary of the memory-transmission-rate tradeoff for several small cases, for which we obtain a set of tight outer bounds. General hypotheses on the optimal tradeoff region are formed from these computed data, which are then analytically proven. This leads to a complete characterization of the optimal tradeoff for systems with only two users, and certain partial characterization for systems with only two files. Next, we show that by carefully analyzing the joint entropy structure of the outer bounds for certain cases, a novel code construction can be reverse-engineered, which eventually leads to a general class of codes. Finally, we show that outer bounds can be computed through strategically relaxing the LP in different ways, which can be used to explore the problem computationally. This allows us firstly to deduce generic characteristic of the converse proof, and secondly to compute outer bounds for larger problem cases, despite the seemingly impossible computation scale.