Communication Complexity and Circuit Complexity

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

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.