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; 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.

复杂性理论的一个主要挑战是证明在一般计算模型中计算给定函数所需的步骤数量。重要的是要有帮助找出我们希望为特定问题实现的最有效解决方案是什么。有一些方法可以证明某些重要的计算模型的限制版本强大的下限。但是，没有足够强大的技术能够证明特定计算问题的固有复杂性很强的范围。拟议的研究的长期目标是找到新的方法来证明复杂性下限并确定布尔函数的数学属性，从而确定其计算复杂性的数学属性。通信协议。提案中考虑的所有模型都与一些重要的计算资源有关。因此，在任何这些模型的不受限制版本中，在特定布尔函数的复杂性上证明了强大的下限将代表更好地理解计算任务的固有复杂性。由于这些模型与布尔电路模型的联系，所考虑的几种问题和方法可能有可能提供新的技术来攻击复杂性理论中的基本开放问题。从各种应用程序的角度来看，提案中考虑的问题本身也很有趣，包括诸如秘密共享方案，私人多方计算和数据结构之类的加密应用程序。该提案中考虑的问题的共同主题是它们与通信复杂性的联系。不同模型中的几种已知下限技术基于与通信复杂性有关的技术。拟议的研究计划进一步探索了这些联系。