AF: Small: Polynomials, Communication, and Query Complexity

University Of California-Los Angeles, Los Angeles CA

Investigators

Abstract

Representations of computational objects by real polynomials play a central role in theoretical computer science. This project focuses on a particularly natural and important representation, known as pointwise approximation. Over the past three decades, pointwise approximation has enabled breakthroughs in the study of a broad spectrum of computational phenomena, including quantum query algorithms, communication protocols, Boolean circuits, learning algorithms, and differential privacy. The investigator will tackle challenging open questions in the pointwise approximation of Boolean functions as well as related questions in communication and quantum query complexity. Their resolution will be a significant advance in these research areas and will have far-reaching consequences elsewhere, including learning theory, circuit complexity, and graph complexity. This project is an ample source of research problems at various levels of difficulty and will be used in advising students. The investigator will integrate this project into his graduate and undergraduate teaching, promote theory research in the Los Angeles area, and mentor underrepresented students in theoretical computer science. The first component of this project takes aim at central open problems in the pointwise approximation of Boolean functions, including proving an optimal direct sum theorem for approximate degree, obtaining depth-optimal lower bounds on the threshold degree and sign-rank of constant-depth circuits, and settling the approximate degree of key functions. In the second component of the project, the investigator plans to leverage polynomial approximation techniques to tackle longstanding open problems in communication complexity theory. Here, the objectives include obtaining strong lower bounds for the polynomial hierarchy (PH) in communication and settling the randomized communication complexity of the set disjointness problem in the notoriously difficult number-on-the-forehead k-party model. The third component of this project is devoted to quantum query complexity, where the investigator aims to settle the quantum query complexity of the k-element distinctness problem and prove a fundamental conjecture of Aaronson and Ambainis on the relation between real polynomials and decision trees. 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.