AF: Small: Polynomials, Communication, and Query Complexity

AF：小：多项式、通信和查询复杂性

• 批准号: 2220232
• 负责人: Alexander Sherstov
• 金额: $ 60万
• 依托单位: University of California-Los Angeles
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-10-01 至 2025-09-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2220232&HistoricalAwards=false
• 关键词: AF; Small; Polynomials; Communication; Query

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.

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