CAREER: Limits of Communication

考虑一个函数，它的参数分布在几个参与方之间，使得任何一方都不可能孤立地计算它。通信复杂性理论研究需要多少通信比特来评估函数。30多年前，由Andrew Yao开创的通信复杂性已经成为理论计算机科学的一个中心研究领域。首先，学习交际作为一种有限的资源具有很强的实践动机。此外，许多其他计算模型中的开放性问题被简化为关于通信的问题。迄今为止，通信复杂性理论几乎影响了理论计算机科学的每一个学科，从图灵机和电路等经典模型到数据结构、学习理论和量子计算等最新主题。该奖项旨在研究通信复杂性理论中三个长期存在的开放性问题：(i)多方通信的局限性；（ii）存在量词和全称量词交替使用时交流的局限性；（三）对组合传播观和矩阵传播观的等价性的推测。这些问题的解决将对理论计算机科学产生重大影响，而不仅仅是通信，包括ACC电路和神经网络的下界，DNF公式的有效学习，以及量子和经典通信的等效。提出的问题的进展将利用其他学科的见解，并为机器学习和矩阵理论提供新的想法。该奖项为不同难度水平的研究问题提供了充足的来源，并将用于指导学生和教授新的研究生和本科课程。作为该奖项的一个组成部分，PI将促进洛杉矶地区的理论研究，并积极参与科学传播。

Consider a function whose arguments are distributed among several parties, making it impossible for any one party to compute it in isolation. Communication complexity theory studies how many bits of communication are needed to evaluate the function. Pioneered by Andrew Yao over thirty years ago, communication complexity has become a central research area in theoretical computer science. First of all, studying communication as a limited resource has a strong practical motivation. Moreover, open problems in many other computational models reduce to questions about communication. To date, communication complexity theory has impacted almost every subject in theoretical computer science, from classical models such as Turing machines and circuits to more recent topics such as data structures, learning theory, and quantum computing.This award takes aim at studying three longstanding open questions in communication complexity theory: (i) the limits of multiparty communication; (ii) the limits of communication with alternating existential and universal quantifiers; (iii) the conjectured equivalence of the combinatorial and matrix-theoretic views of communication. A resolution of these questions would have major consequences in theoretical computer science beyond communication, including lower bounds for ACC circuits and neural networks, efficient learning of DNF formulas, and an equivalence of quantum and classical communication. Progress on the proposed problems will exploit insights from, and contribute new ideas to, other disciplines such as machine learning and matrix theory. This award provides an ample source of research problems at various levels of difficulty and will be used in advising students and teaching new graduate and undergraduate courses. As an integral part of the award, the PI will promote theory research in the Los Angeles area and take an active part in scientific dissemination.