课题基金 / 基金详情

AF: Small: Foundational Research in Communication Complexity and Its Applications

AF: Small: Foundational Research in Communication Complexity and Its Applications
AF:小型:通信复杂性及其应用的基础研究
批准号:
1217375
负责人:
Amit Chakrabarti
金额:
$44.0万
依托单位:
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2012
资助国家:
美国
项目状态:
已结题
起止时间:
2012-09-01 至 2016-08-31

项目摘要

项目成果

Amit Chakrabarti的其他基金

相似基金

相关文献

中文摘要
翻译
通信复杂性是对计算问题的研究,其中输入被分散在多个位置,被描述为玩通信游戏的各方。这些各方必须根据协议相互通信以解决感兴趣的问题,同时最小化通信量(交换的比特数)。除了它的内在动机(被即将到来的云计算时代所增强),通信复杂性的重要性来自于它对理论计算机科学的所有其他领域的影响,甚至是那些不直接涉及通信的领域;例如电路复杂性、数据流、查询复杂性、性能测试和博弈论。在这个奖项下,PI和他的学生将研究一些具体的通信游戏,不仅试图在具体问题上建立新的界限,而且通过新的技术和范例拓宽该领域的基础。由此发现的结果和想法将应用于上面提到的一些领域,特别是数据流算法。一些具有代表性的研究目标如下。(1)发展Merlin-Arthur通信理论,以期应用于与强大但不可信的助手交互的数据流算法。(2)通过新的通信下界或改进的算法,加深了我们对许多图流传输问题的理解。(3)将最新的信息复杂性技术与旧的通信复杂性分析技术联系起来。该奖项的更广泛影响包括培训最多两名研究生,他们可能从事通信复杂性或其应用的任何方面的工作,以及设计和教学一门新的关于通信协议和复杂性的研究生课程。所取得的成果将在其他机构的国际会议、有针对性的讲习班和研讨会上传播。
英文摘要
Communication complexity is the study of computational problems where the input is split amongst multiple locations, described as parties playing a communication game. These parties must communicate with one another according to a protocol to solve the problem of interest, while minimizing the amount of communication (number of bits exchanged). Besides its intrinsic motivation (enhanced by the coming "cloud computing" era), communication complexity derives its importance from its implications in all sorts of other areas of theoretical computer science, even ones that do not directly involve communication; examples are circuit complexity, data streaming, query complexity, property testing, and game theory.Under this award, the PI and his students will investigate a number of concrete communication games, attempting not just to establish new bounds on specific problems, but also to broaden the foundations of the field through new techniques and paradigms. Results and ideas thus discovered will be applied to some of the areas mentioned above, with a particular focus on data stream algorithms. Some representative research goals are as follows. (1) Developing the theory of Merlin-Arthur communication, with a view towards applications to data stream algorithms that interact with a powerful but untrusted helper. (2) Deepening our understanding of a number of graph streaming problems, either through new communication lower bounds or improved algorithms. (3) Relating the recent technique of information complexity to older established techniques for analyzing communication complexity.The broader imapcts of the award include the training of up to two graduate students who may work on any aspect of communication complexity or its applications, and the design and teaching of a new graduate-level course on communication protocols and complexity. Results obtained will be disseminated at international conferences, targeted workshops and seminars at other institutions.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
AF: CIF: Small: Communication complexity techniques beyond classical information theory
  • 批准号:
    2006589
  • 项目类别:
    Standard Grant
  • 资助金额:
    $49.76万
  • 财政年份:
    2020
  • 负责人:
    Amit Chakrabarti
  • 依托单位:
AF: Small: Collaborative Research: New Challenges in Graph Stream Algorithms and Related Communication Games
  • 批准号:
    1907738
  • 项目类别:
    Standard Grant
  • 资助金额:
    $25.0万
  • 财政年份:
    2019
  • 负责人:
    Amit Chakrabarti
  • 依托单位:
AF: EAGER: Data Streaming with a View towards Cloud Computing
  • 批准号:
    1650992
  • 项目类别:
    Standard Grant
  • 资助金额:
    $30.0万
  • 财政年份:
    2016
  • 负责人:
    Amit Chakrabarti
  • 依托单位:
DC: Small: Data Streaming through a Complexity-Theoretic Lens
  • 批准号:
    0916565
  • 项目类别:
    Standard Grant
  • 资助金额:
    $33.65万
  • 财政年份:
    2009
  • 负责人:
    Amit Chakrabarti
  • 依托单位:
国内基金
海外基金
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
  • 批准号:
  • 项目类别:
    省市级项目
  • 资助金额:
    --
  • 批准年份:
    2024
  • 负责人:
  • 依托单位:
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
  • 批准号:
  • 项目类别:
    省市级项目
  • 资助金额:
    10.0万元
  • 批准年份:
    2022
  • 负责人:
    张祥忠
  • 依托单位:
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
  • 批准号:
    31972324
  • 项目类别:
    面上项目
  • 资助金额:
    58.0万元
  • 批准年份:
    2019
  • 负责人:
    高学文
  • 依托单位: