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电路、数据结构、密码学、学习理论和分布式计算等不同领域有许多应用。这个项目的重点是探索通信复杂性和其他计算模型中计算问题的复杂性之间的联系。本研究的主要目标是开发新的技术来证明通信复杂性的下界，并使用这些方法来获得其他模型中的资源下界。该项目解决了随机和多方通信复杂性、私有信息检索以及估计数据流算法的空间需求等问题。关于各种资源的特定函数的复杂度下界的证明一直是复杂度理论中最具挑战性的领域之一。通信复杂性的争论和源于通信复杂性的技术已经成为几个下界结果的核心，这些结果处于当前技术可实现的边界。这个项目可能会带来解决复杂性理论中基本问题的新方法。