CIF: Small: Information Flow in Networks: Entropy, Matroids and Groups

这项研究旨在开发一种基于优化的网络信息理论方法，远远超出当前的网络理论和实践。近来，许多用户通过有线和无线网络同时传输信息的问题引起了人们的极大兴趣。信息论很有可能对这种未来网络的设计和维护方式产生影响，这既是因为有线网络对于网络编码(其中信息流实际上是组合而不是简单地路由)等应用程序来说已经成熟，也因为使用传统的网络工具无法令人满意地处理无线网络。挑战在于，即使是最简单的网络信息理论问题也是出了名的难，因此，信息理论无法为网络从业者提供许多工具。这项研究旨在通过开发工具来更有效地进行网络设计来纠正这种情况。虽然从原则上讲，在有线网络中可以通过在熵向量空间上的凸优化来获得信息论速率，但这一努力严重阻碍了这一努力，因为似乎无法获得对熵空间的显式表征。为了绕过这一点，研究将考虑框架，虽然可能不是最优的，但适用于任意网络，具有合理的复杂性，并适合于分布式实施。所采取的数学方法是四重的，并利用拟阵的表示理论(设计线性网络码)、蒙特卡洛马尔科夫链方法来分布式地设计“好的”网络码、利用群论技术从非阿贝尔群构造非线性网络码、以及利用行列式不等式来研究熵空间。

This research aims to develop an optimization-based approach to network information theory, that goes well beyond current networking theory and practice. There is a great deal of recent interest in the problem of simultaneous information transmission among many users over wired and wireless networks. Information theory is well poised to have an impact on the manner in which such future networks are designed and maintained, both because wired networks are ripe for applications such as network coding (where information streams are actually combined rather than simply routed) and also because wireless networks cannot be satisfactorily dealt with using conventional networking tools. The challenge is that even the simplest network information theory problems are notoriously difficult and, as a result, information theory has not been able to provide many tools to network practitioners. The research aims to remedy this situation by developing tools for more effective network design. While, in principle, it is possible to obtain the information-theoretic rates in wired networks via convex optimization over the space of entropy vectors, this effort is severely hampered by the fact that an explicit characterization of the entropic space does not appear to be within reach. To circumvent this, the research will consider frameworks that, while possibly suboptimal, apply to arbitrary networks, have reasonable complexity and lend themselves to distributed implementation. The mathematical approach taken is four-fold and makes use of the representation theory of matroids (to design linear network codes), Monte Carlo Markov chain methods to distributedly design "good" network codes, group-theoretic techniques to construct nonlinear network codes from non-Abelian groups, and determinantal inequalities to study the entropic space.