Communication Complexity and Applications

计算的许多方面可以被视为交流过程。通信复杂性是一种数学理论，旨在估计此类过程所需的通信量。通信复杂性参数可用于估计计算所需的各种其他资源，包括时间和空间(内存)和电路大小。通信复杂性在计算机网络、VLSI电路、数据结构、密码学、学习理论和分布式计算等领域有着广泛的应用，本课题致力于探索通信复杂性与其他计算模型中计算问题的复杂性之间的联系。这项研究的主要目的是开发新的技术来证明通信复杂性的下界，并使用这些方法在其他模型中获得资源的下界。该项目解决了随机化和多方通信的复杂性、隐私信息检索以及估计数据流算法的空间需求等问题。证明特定功能相对于各种资源的复杂性下界一直是复杂性理论中最具挑战性的领域之一。源于通信复杂性的通信复杂性论证和技术一直处于几个下限结果的核心，这些下限结果处于当前技术可实现的边界。该项目可能会为解决复杂性理论中的基本问题带来新的方法。

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.