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 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。