AF: Small: Polynomials, Communication, and Query Complexity

用实多项式表示计算对象在理论计算机科学中起着核心作用。这个项目的重点是一个特别自然和重要的表示，被称为点逼近。在过去的三十年里，点向近似在广泛的计算现象研究中取得了突破，包括量子查询算法、通信协议、布尔电路、学习算法和微分隐私。研究者将解决布尔函数的点向逼近以及通信和量子查询复杂性相关问题中具有挑战性的开放问题。他们的解决方案将是这些研究领域的重大进步，并将在其他领域产生深远的影响，包括学习理论，电路复杂性和图复杂性。这个项目是各种困难程度的研究问题的充足来源，并将用于指导学生。研究者将把该项目整合到他的研究生和本科教学中，促进洛杉矶地区的理论研究，并指导理论计算机科学领域代表性不足的学生。本课题的第一部分针对布尔函数的点向逼近中的中心开放问题，包括证明近似度的最优直接和定理，获得定深电路的阈值度和符号秩的深度最优下界，以及确定关键函数的近似度。在该项目的第二个组成部分，研究者计划利用多项式近似技术来解决通信复杂性理论中长期存在的开放性问题。在这里，目标包括获得通信中多项式层次结构（PH）的强下界，以及解决众所周知的困难数字-额头k-party模型中集合不连接问题的随机通信复杂性。该项目的第三部分致力于量子查询复杂性，其中研究者旨在解决k元素独特性问题的量子查询复杂性，并证明Aaronson和Ambainis关于实多项式与决策树之间关系的一个基本猜想。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.