AF: Small: Multiparty Communication, Polynomials, and Noise

通信复杂性理论研究计算参数分布在多方的函数所需的最小通信量（以比特为单位）。除了研究通信作为瓶颈资源的基本重要性之外，该理论在许多领域都有大量的应用，包括机器学习、机制设计、流算法、数据结构、伪随机生成器和VLSI布局。这个项目解决了一些基本问题，这些问题的解决将对该学科产生重大影响。这项工作将利用其他领域的见解，并为量子计算、计算学习和近似理论提供新的想法。该项目是各种困难程度的研究问题的充足来源，并将用于指导研究生和本科生。研究者将把本研究融入研究生和本科教学中，积极参与科学传播，推动南加州理论计算机科学的发展。这个项目包括两个相关的部分。首先，研究者将解决长期以来在多方通信研究中的开放性问题，如解决集合不连接问题的通信要求和打破多方通信下界的对数障碍。第二个，这个项目的补充组成部分将推进布尔函数的解析表示的研究。在这里，研究者的目标是获得多项式近似和k元素区别函数，等深度电路和任意深度的布尔公式的符号表示的紧下界。这个项目的两个研究组成部分是密切相关的，因为它们需要同一类分析技术。事实上，在过去二十年中，通信复杂性的主要进展是通过将通信协议显式或隐式地转换为具有相当复杂性的多元多项式并通过分析由此产生的近似问题而获得的。对多方通信和多项式的计划研究通过对噪声的关注进一步统一，在不完全输出或中间计算的对抗性损坏的意义上。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Communication complexity theory studies the minimum amount of communication, measured in bits, required in order to compute functions whose arguments are distributed among several parties. In addition to the basic importance of studying communication as a bottleneck resource, the theory has found a vast number of applications in many areas, including machine learning, mechanism design, streaming algorithms, data structures, pseudo-random generators, and VLSI layouts. This project tackles fundamental questions whose resolution will have a significant impact on the discipline. This work will exploit insights from, and contribute new ideas to, other areas such as quantum computing, computational learning, and approximation theory. The project is an ample source of research problems at various levels of difficulty and will be used in advising graduate and undergraduate students. The investigator will integrate this research into his graduate and undergraduate teaching, take an active part in scientific dissemination, and promote theoretical computer science in Southern California.This project comprises two related components. First, the investigator will tackle longstanding open problems in the study of multiparty communication, such as settling the communication requirements of the set disjointness problem and breaking the logarithmic barrier for multiparty communication lower bounds. The second, complementary component of this project will advance the study of analytic representations of Boolean functions. Here, the investigator aims to obtain tight lower bounds for the polynomial approximation and sign-representation of the k-element distinctness function, constant-depth circuits, and Boolean formulas of arbitrary depth. The two research components of this project are intimately related in that they require the same class of analytic techniques. Indeed, major advances in communication complexity over the past two decades have been obtained by transforming, explicitly or implicitly, communication protocols into multivariate polynomials of comparable complexity and by analyzing the resulting approximation questions. The planned research on multiparty communication and polynomials is further unified by a focus on noise, in the sense of imperfect output or adversarial corruption of intermediate computations.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.