Communication Complexity and Applications

通信复杂性和应用

• 批准号: 0830756
• 负责人: Anna Gal
• 金额: $ 20万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-09-01 至 2011-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0830756&HistoricalAwards=false
• 关键词: Communication; Complexity; Applications

Many aspects of computation can be viewed as communication processes. Communication complexity is the mathematical theory aimed at estimating the amount of communication necessary for such processes. Communication complexity arguments can be used to provide estimates on various other resources needed for computation, including time and space (memory) and circuit size. Communication complexity has many applications in different areas including computer networks, VLSI circuits, data structures, cryptography, learning theory and distributed computing.This project focuses on exploring the connections between communication complexity and the complexity of computational problems in other models of computation. The main objectives of this research are developing new techniques for proving lower bounds on communication complexity, and using these methods to obtain lower bounds on resources in other models. The project addresses problems of randomized and multiparty communication complexity, private information retrieval, and estimating the space requirements of data stream algorithms.Proving lower bounds on the complexity of specific functions with respect to various resources has been one of the most challenging areas in complexity theory. Communication complexity arguments and techniques originating from communication complexity have been at the core of several lower bound results that are at the boundary of what is achievable by current techniques. The project can potentially lead to new methods for attacking fundamental problems in complexity theory.

计算的许多方面都可以看作是通信过程。 沟通复杂性是旨在估计此类过程所需的沟通量的数学理论。 通信复杂性参数可用于对计算所需的各种其他资源（包括时间和空间（内存）和电路大小）提供估计。 通信复杂性在不同领域的应用程序有许多应用程序，包括计算机网络，VLSI电路，数据结构，密码学，学习理论和分布式计算。本项目着重于探索其他计算模型中通信复杂性与计算问题的复杂性之间的连接。 这项研究的主要目标是开发新技术，以证明通信复杂性的下限，并使用这些方法来获得其他模型中资源的下限。 该项目解决了随机和多方交流复杂性，私人信息检索的问题，并估算了数据流算法的空间要求。对特定功能相对于各种资源的复杂性进行下限是复杂性理论中最具挑战性的领域之一。 源自通信复杂性的通信复杂性参数和技术一直是几个下限结果的核心，​​这些结果处于当前技术可实现的边界。 该项目可能会导致新的方法来攻击复杂性理论中的基本问题。