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-party模型中解决集合脱节问题的随机通信复杂性。该项目的第三个组成部分致力于量子查询的复杂性，调查人员的目的是解决K元素独特性问题的量子查询复杂性，并证明了Aaronson和Ambainis的基本猜想和Ambainis对真实的多项式和决策树之间的关系。这些奖项通过NSF的统治范围来依据，这反映了NSF的合法传统和依据的范围。 标准。