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

AF：小：RUI：柯尔莫哥洛夫复杂性和网络信息理论的新方向

基本信息

批准号：
1811729
负责人：
Marius Zimand
金额：
$ 23.62万
依托单位：
Towson University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-10-01 至 2022-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1811729&HistoricalAwards=false
关键词：
AF Small RUI New Directions

项目摘要

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.

具有多个发件人和接收器的系统中的数据通信会引起由于复杂的数据相关模式，网络拓扑和交互情况而引起的困难问题。传统上，这些问题是使用信息理论（IT）的工具解决的，该工具假设数据是根据某种生成模型生成的。实际上，大多数情况下，生成模型尚不清楚。即使已知，它通常比理论研究中通常使用的模型更为复杂。该项目将使用算法信息理论（AIT，也称为Kolmogorov复杂性）中的工具，该工具将数据中的信息等同于其最小的描述长度。优势在于，新方法不依赖任何模型，因此在更一般的情况下获得的结果是有效的。将研究的问题引起了计算机科学家，电气工程师和数学家的关注。该项目将在这些社区之间促进思想的深刻而动态的交流。该项目将在Kolmogorov复杂性和沟通复杂性方面产生新的见解。这些领域在计算复杂性，机器学习，建设性组合学和其他领域中都有应用。结果可能会在许多此类领域产生影响。该项目将允许本科生和研究生参加具有强烈理论风味和现实应用程序的希望的研究活动。该项目是及时且现实的，因为最近已经显而易见的是，一些有趣的问题（例如，非癌细胞来源的来源编码），这些问题无法与基于Shannon的工具来解决Shannon，可以在Shannon的工具中求解，可以在AIT框架中解决。在另一个方向上，从结果和技术中启发的Kolmogorov复杂性中的某些经典问题最近取得了进展。该项目将：（1）隔离，理解和发展Kolmogorov复杂性的某些方面与数据通信特别相关；（2）使用新开发的工具在网络通信（例如渠道编码，网络编码，交互式协议等）中取得成功的进展；（3）使用沟通环境中的见解来推进科尔莫格罗夫复杂性的理论。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛的影响评估标准通过评估来支持的。

项目成果

期刊论文数量（4）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Secret Key Agreement from Correlated Data, with No Prior Information

相关数据的密钥协议，无需先验信息

DOI：
10.4230/lipics.stacs.2020.21
发表时间：
2020
期刊：
37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020
影响因子：
0
作者：
Zimand, Marius
通讯作者：
Zimand, Marius

Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity

时限柯尔莫哥洛夫复杂度中的最优编码定理