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

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

基本信息

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

项目摘要

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复杂性和通信复杂性。这些领域在计算复杂性、机器学习、构造组合学和其他领域都有应用。这些结果可能会对其中许多领域产生影响。该项目将允许本科生和研究生参与具有浓厚理论色彩和现实应用前景的研究活动。该项目是及时和现实的,因为最近已经变得明显,一些有趣的问题(例如,非遍历信源的信源编码),这不能用基于香农熵的工具来处理,可以在AIT框架中解决。在另一个方向上,最近在Kolmogorov复杂性的一些经典问题上取得了进展,这些问题受到IT结果和技术的启发。该项目将:(1)分离、理解和发展Kolmogorov复杂性的某些方面,这些方面与数据通信特别相关;(2)利用新开发的工具,在信道编码、网络编码、交互协议等网络通信中的突出问题上取得进展,及其他;以及(3)使用来自通信环境的见解来推进Kolmogorov复杂性理论。该奖项反映了NSF的法定使命,并通过使用基金会的知识价值和更广泛的影响审查标准进行评估而被认为值得支持。

项目成果

期刊论文数量(4)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Secret Key Agreement from Correlated Data, with No Prior Information
相关数据的密钥协议,无需先验信息
Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity
时限柯尔莫哥洛夫复杂度中的最优编码定理
  • DOI:
  • 发表时间:
    2022
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Lu, Zhenjian;Oliveira, Igor C.;Zimand, Marius
  • 通讯作者:
    Zimand, Marius
27 Open Problems in Kolmogorov Complexity
27 柯尔莫哥洛夫复杂度中的开放问题
  • DOI:
    10.1145/3510382.3510389
  • 发表时间:
    2021
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Romashchenko, Andrei;Shen, Alexander;Zimand, Marius
  • 通讯作者:
    Zimand, Marius
An Operational Characterization of Mutual Information in Algorithmic Information Theory
  • DOI:
    10.1145/3356867
  • 发表时间:
    2019-09-01
  • 期刊:
  • 影响因子:
    2.5
  • 作者:
    Romashchenko, Andrei;Zimand, Marius
  • 通讯作者:
    Zimand, Marius
{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Marius Zimand其他文献

Hall-type theorems for fast dynamic matching and applications
快速动态匹配的霍尔型定理及应用
  • DOI:
  • 发表时间:
    2022
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Bruno Bauwens;Marius Zimand
  • 通讯作者:
    Marius Zimand
Several Remarks on Index Generation Functions
关于索引生成函数的几点说明
On Optimal Language Compression for Sets in PSPACE/poly
PSPACE/poly 中集合的最优语言压缩
  • DOI:
    10.1007/s00224-014-9535-y
  • 发表时间:
    2013
  • 期刊:
  • 影响因子:
    0.5
  • 作者:
    N. V. Vinodchandran;Marius Zimand
  • 通讯作者:
    Marius Zimand
Polynomial-Time Semi-Rankable Sets
多项式时间半可排序集
  • DOI:
    10.21236/ada300061
  • 发表时间:
    1996
  • 期刊:
  • 影响因子:
    0
  • 作者:
    L. Hemaspaandra;Mohammed J. Zaki;Marius Zimand
  • 通讯作者:
    Marius Zimand
The Complexity of Finding Top-Toda-Equivalence-Class Members
寻找顶级 Toda 等价类成员的​​复杂性
  • DOI:
    10.1007/s00224-005-1211-9
  • 发表时间:
    2004
  • 期刊:
  • 影响因子:
    0.5
  • 作者:
    L. Hemaspaandra;Mitsunori Ogihara;Mohammed J. Zaki;Marius Zimand
  • 通讯作者:
    Marius Zimand

Marius Zimand的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Marius Zimand', 18)}}的其他基金

AF: Small: Studies in Randomness Extraction
AF:小:随机性提取的研究
  • 批准号:
    1016158
  • 财政年份:
    2010
  • 资助金额:
    $ 23.62万
  • 项目类别:
    Continuing Grant
New Directions in the Study of Randomness Extractors
随机性提取器研究的新方向
  • 批准号:
    0634830
  • 财政年份:
    2006
  • 资助金额:
    $ 23.62万
  • 项目类别:
    Standard Grant

相似国自然基金

昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
  • 批准号:
  • 批准年份:
    2024
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
  • 批准号:
    n/a
  • 批准年份:
    2022
  • 资助金额:
    10.0 万元
  • 项目类别:
    省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
  • 批准号:
    32000033
  • 批准年份:
    2020
  • 资助金额:
    24.0 万元
  • 项目类别:
    青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
  • 批准号:
    31972324
  • 批准年份:
    2019
  • 资助金额:
    58.0 万元
  • 项目类别:
    面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
  • 批准号:
    81900988
  • 批准年份:
    2019
  • 资助金额:
    21.0 万元
  • 项目类别:
    青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
  • 批准号:
    31870821
  • 批准年份:
    2018
  • 资助金额:
    56.0 万元
  • 项目类别:
    面上项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
  • 批准号:
    31802058
  • 批准年份:
    2018
  • 资助金额:
    26.0 万元
  • 项目类别:
    青年科学基金项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
  • 批准号:
    31772128
  • 批准年份:
    2017
  • 资助金额:
    60.0 万元
  • 项目类别:
    面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
  • 批准号:
    81704176
  • 批准年份:
    2017
  • 资助金额:
    20.0 万元
  • 项目类别:
    青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
  • 批准号:
    91640114
  • 批准年份:
    2016
  • 资助金额:
    85.0 万元
  • 项目类别:
    重大研究计划

相似海外基金

AF: Small: RUI: Toward High-Performance Block Krylov Subspace Algorithms for Solving Large-Scale Linear Systems
AF:小:RUI:用于求解大规模线性系统的高性能块 Krylov 子空间算法
  • 批准号:
    2327619
  • 财政年份:
    2023
  • 资助金额:
    $ 23.62万
  • 项目类别:
    Standard Grant
Collaborative Research: AF: Small: RUI: Data Science from Economic Foundations
合作研究:AF:小型:RUI:来自经济基础的数据科学
  • 批准号:
    2218814
  • 财政年份:
    2022
  • 资助金额:
    $ 23.62万
  • 项目类别:
    Standard Grant
Collaborative Research: AF: Small: RUI: Data Science from Economic Foundations
合作研究:AF:小型:RUI:来自经济基础的数据科学
  • 批准号:
    2218813
  • 财政年份:
    2022
  • 资助金额:
    $ 23.62万
  • 项目类别:
    Standard Grant
AF: Small: RUI: Towards Resolving the Dynamic Optimality Conjecture.
AF:小:RUI:解决动态最优猜想。
  • 批准号:
    1910873
  • 财政年份:
    2019
  • 资助金额:
    $ 23.62万
  • 项目类别:
    Standard Grant
AF: Small: RUI: Competitive Search, Evacuation and Reconfiguration with Coordinated Mobile Agents
AF:小型:RUI:通过协调移动代理进行竞争性搜索、疏散和重新配置
  • 批准号:
    1813940
  • 财政年份:
    2018
  • 资助金额:
    $ 23.62万
  • 项目类别:
    Standard Grant
AF: Small: RUI: Unifying Self-Assembly Through Tile Automata
AF:小:RUI:通过平铺自动机统一自组装
  • 批准号:
    1817602
  • 财政年份:
    2018
  • 资助金额:
    $ 23.62万
  • 项目类别:
    Standard Grant
AF: Small: RUI: The model-based approach and a new kind of Cylindrical Algebraic Decomposition
AF:小:RUI:基于模型的方法和一种新型圆柱代数分解
  • 批准号:
    1525896
  • 财政年份:
    2015
  • 资助金额:
    $ 23.62万
  • 项目类别:
    Interagency Agreement
AF: Small: RUI: Faster Arithmetic for Sparse Polynomials and Integers
AF:小:RUI:稀疏多项式和整数的更快算术
  • 批准号:
    1319994
  • 财政年份:
    2013
  • 资助金额:
    $ 23.62万
  • 项目类别:
    Interagency Agreement
AF: Small: RUI: A new and improved algorithm for fitting RNA backbone in crystallographic data
AF:小:RUI:一种新的改进算法,用于在晶体学数据中拟合 RNA 主链
  • 批准号:
    1218145
  • 财政年份:
    2012
  • 资助金额:
    $ 23.62万
  • 项目类别:
    Standard Grant
AF: Small: RUI: Network design and facility location problems
AF:小:RUI:网络设计和设施选址问题
  • 批准号:
    1218620
  • 财政年份:
    2012
  • 资助金额:
    $ 23.62万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了