AF: Small: RUI: New Directions in Kolmogorov Complexity and Network Information Theory

在具有多个发送方和接收方的系统中的数据通信带来了由复杂的数据关联模式、网络拓扑和交互场景的可能性引起的难题。传统上，这些问题是使用信息论(IT)中的工具来解决的，该理论假设数据是根据特定的生成模型产生的。在实践中，大多数情况下，生成模型是未知的。即使它是已知的，它也往往比理论研究中通常使用的模型更复杂。这个项目将使用算法信息论(AIT，也称为柯尔莫戈洛夫复杂性)的工具，它将数据中的信息等同于其最小描述长度。优点是新方法不依赖于任何模型，因此这种方法得到的结果在更一般的情况下是有效的。计算机科学家、电气工程师和数学家对将要研究的问题感兴趣。该项目将促进这些社区之间深入而充满活力的思想交流。该项目将对科尔莫戈罗夫复杂性和通信复杂性产生新的见解。这些领域在计算复杂性、机器学习、构造性组合学等领域都有应用。这一结果可能会对其中许多领域产生影响。该项目将允许本科生和研究生参与具有强烈理论气息和现实应用前景的研究活动。该项目是及时和现实的，因为最近变得明显的是，一些有趣的问题(例如，非遍历源的源代码编码)可以在AIT框架中解决，这些问题无法用基于香农熵的工具来解决。另一方面，最近在Kolmogorov复杂性的一些经典问题上取得了进展，这些问题的灵感来自于IT的结果和技术。该项目将：(1)分离、理解和发展柯尔莫戈罗夫复杂性中与数据通信特别相关的某些方面；(2)使用新开发的工具在网络通信中的突出问题上取得进展，如信道编码、网络编码、交互协议和其他；以及(3)利用通信环境中的见解来推进柯尔莫戈罗夫复杂性理论。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Data communication in systems with multiple senders and receivers raises difficult problems caused by the possibility of complex data correlation patterns, network topologies, and interaction scenarios. Traditionally, these problems have been tackled using tools from Information Theory (IT), which assumes that the data has been produced according to a certain generative model. In practice, most of the time the generative model is not known. Even if it is known, it is often more complicated than the models typically used in theoretical studies. This project will use tools from Algorithmic Information Theory (AIT, also known as Kolmogorov complexity), which equates the information in a piece of data with its minimal description length. The advantage is that the new approach does not rely on any model, and consequently the results obtained this way are valid in more general circumstances. The problems that will be studied are of interest to computer scientists, electrical engineers, and mathematicians. The project will promote a deep and dynamic exchange of ideas between these communities. This project will produce new insights in Kolmogorov complexity and communication complexity. These areas have applications in computational complexity, machine learning, constructive combinatorics, and other fields. The results will likely have an impact in many of these areas. The project will allow undergraduate and graduate students to participate in research activities that have a strong theoretical flavor and the promise of real-world applications.The project is timely and realistic because it has recently become apparent that some interesting questions (for instance, source coding of non-ergodic sources), which cannot be approached with tools based on Shannon entropy, can be solved in the AIT framework. In the other direction, there has been recent progress in some classical problems in Kolmogorov complexity inspired from results and techniques from IT. The project will: (1) isolate, understand, and develop certain aspects of Kolmogorov complexity that are particularly relevant for data communication; (2) use the newly-developed tools to make progress in outstanding problems in network communication such as channel coding, network coding, interactive protocols, and others; and (3) use the insights from the communication setting to advance the theory of Kolmogorov complexity.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.