Communication Complexity and Circuit Complexity

通信复杂性和电路复杂性

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

A major challenge in complexity theory is to prove lower bounds on the number of steps necessary to compute a given function in general computational models. It would be important to have techniques that help to find out what is the most efficient solution we can hope to achieve for specific problems. There are methods for proving strong lower bounds for restricted versions of some important models of computation. However, there are no known techniques powerful enough to prove strong lower bounds on the intrinsic complexity of specific computational problems.The long term objective of the proposed research is finding new methods for proving complexity lower bounds and identifying mathematical properties of Boolean functions that determine their computational complexity.The specific plan of research outlined in the proposal involves the analysis of problems in various computational models, such as the cell probe model, branching programs, span programs, and multiparty communication protocols. All the models considered in the proposal are related to some important computational resource. Thus proving strong lower bounds on the complexity of specific Boolean functions in the unrestricted versions of any of these models would represent significant progress towards better understanding the inherent complexity of computational tasks. Because of the connections of these models to the Boolean circuit model, several of the problems and approaches considered may potentially provide new techniques to attack fundamental open problems in complexity theory. The problems considered in the proposal are also interesting on their own right from the point of view of various applications, including cryptographic applications such as secret sharing schemes, private multiparty computation, and data structures.A common theme of the problems considered in the proposal is their connection to communication complexity. Several of the known lower bound techniques in different models are based on techniques related to communication complexity. The proposed research plans to explore these connections further.

复杂性理论的一个主要挑战是证明在一般计算模型中计算给定函数所需的步数的下界。重要的是，要有技术来帮助找出我们能够希望为具体问题实现的最有效的解决办法。对于一些重要的计算模型的限制版本，有证明强下界的方法。然而，目前还没有足够强大的技术来证明特定计算问题内在复杂性的强下界。提出的研究的长期目标是寻找新的方法来证明复杂性下界和确定布尔函数的数学性质，决定其计算复杂性。提案中概述的具体研究计划涉及各种计算模型中的问题分析，例如细胞探针模型，分支程序，跨度程序和多方通信协议。本文所考虑的所有模型都涉及到一些重要的计算资源。因此，在这些模型的任何无限制版本中证明特定布尔函数复杂性的强下界将代表着更好地理解计算任务的内在复杂性的重大进展。由于这些模型与布尔电路模型的联系，所考虑的一些问题和方法可能会提供新的技术来解决复杂性理论中的基本开放问题。从各种应用程序的角度来看，提案中考虑的问题本身也很有趣，包括加密应用程序，如秘密共享方案、私有多方计算和数据结构。提案中考虑的问题的一个共同主题是它们与通信复杂性的联系。在不同的模型中，一些已知的下界技术是基于与通信复杂性相关的技术。拟议的研究计划进一步探索这些联系。