Communication Complexity and 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.