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.
