AF: Small: Multiparty Communication, Polynomials, and Noise

University Of California-Los Angeles, Los Angeles CA

Investigators

Abstract

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.