AF: Small: Polynomials, Communication, and Query Complexity
AF:小:多项式、通信和查询复杂性
基本信息
- 批准号:2220232
- 负责人:
- 金额:$ 60万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2022
- 资助国家:美国
- 起止时间:2022-10-01 至 2025-09-30
- 项目状态:未结题
- 来源:
- 关键词:
项目摘要
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的法定使命,并通过使用基金会的知识价值和更广泛的影响进行评估,被认为值得支持审查标准。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Alexander Sherstov其他文献
Alexander Sherstov的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Alexander Sherstov', 18)}}的其他基金
AF: Small: Multiparty Communication, Polynomials, and Noise
AF:小:多方通信、多项式和噪声
- 批准号:
1814947 - 财政年份:2018
- 资助金额:
$ 60万 - 项目类别:
Standard Grant
相似国自然基金
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
- 批准号:
- 批准年份:2024
- 资助金额:0.0 万元
- 项目类别:省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
- 批准号:n/a
- 批准年份:2022
- 资助金额:10.0 万元
- 项目类别:省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
- 批准号:32000033
- 批准年份:2020
- 资助金额:24.0 万元
- 项目类别:青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
- 批准号:31972324
- 批准年份:2019
- 资助金额:58.0 万元
- 项目类别:面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
- 批准号:81900988
- 批准年份:2019
- 资助金额:21.0 万元
- 项目类别:青年科学基金项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
- 批准号:31802058
- 批准年份:2018
- 资助金额:26.0 万元
- 项目类别:青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
- 批准号:31870821
- 批准年份:2018
- 资助金额:56.0 万元
- 项目类别:面上项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
- 批准号:31772128
- 批准年份:2017
- 资助金额:60.0 万元
- 项目类别:面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
- 批准号:81704176
- 批准年份:2017
- 资助金额:20.0 万元
- 项目类别:青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
- 批准号:91640114
- 批准年份:2016
- 资助金额:85.0 万元
- 项目类别:重大研究计划
相似海外基金
CSR: Small: Leveraging Physical Side-Channels for Good
CSR:小:利用物理侧通道做好事
- 批准号:
2312089 - 财政年份:2024
- 资助金额:
$ 60万 - 项目类别:
Standard Grant
NeTS: Small: NSF-DST: Modernizing Underground Mining Operations with Millimeter-Wave Imaging and Networking
NeTS:小型:NSF-DST:利用毫米波成像和网络实现地下采矿作业现代化
- 批准号:
2342833 - 财政年份:2024
- 资助金额:
$ 60万 - 项目类别:
Standard Grant
CPS: Small: NSF-DST: Autonomous Operations of Multi-UAV Uncrewed Aerial Systems using Onboard Sensing to Monitor and Track Natural Disaster Events
CPS:小型:NSF-DST:使用机载传感监测和跟踪自然灾害事件的多无人机无人航空系统自主操作
- 批准号:
2343062 - 财政年份:2024
- 资助金额:
$ 60万 - 项目类别:
Standard Grant
Collaborative Research: FET: Small: Reservoir Computing with Ion-Channel-Based Memristors
合作研究:FET:小型:基于离子通道忆阻器的储层计算
- 批准号:
2403559 - 财政年份:2024
- 资助金额:
$ 60万 - 项目类别:
Standard Grant
オミックス解析を用いたブドウ球菌 small colony variants の包括的特徴づけ
使用组学分析全面表征葡萄球菌小菌落变体
- 批准号:
24K13443 - 财政年份:2024
- 资助金额:
$ 60万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
AF: Small: Problems in Algorithmic Game Theory for Online Markets
AF:小:在线市场的算法博弈论问题
- 批准号:
2332922 - 财政年份:2024
- 资助金额:
$ 60万 - 项目类别:
Standard Grant
Collaborative Research: FET: Small: Algorithmic Self-Assembly with Crisscross Slats
合作研究:FET:小型:十字交叉板条的算法自组装
- 批准号:
2329908 - 财政年份:2024
- 资助金额:
$ 60万 - 项目类别:
Standard Grant
NeTS: Small: ML-Driven Online Traffic Analysis at Multi-Terabit Line Rates
NeTS:小型:ML 驱动的多太比特线路速率在线流量分析
- 批准号:
2331111 - 财政年份:2024
- 资助金额:
$ 60万 - 项目类别:
Standard Grant
Collaborative Research: SHF: Small: LEGAS: Learning Evolving Graphs At Scale
协作研究:SHF:小型:LEGAS:大规模学习演化图
- 批准号:
2331302 - 财政年份:2024
- 资助金额:
$ 60万 - 项目类别:
Standard Grant
Collaborative Research: SHF: Small: LEGAS: Learning Evolving Graphs At Scale
协作研究:SHF:小型:LEGAS:大规模学习演化图
- 批准号:
2331301 - 财政年份:2024
- 资助金额:
$ 60万 - 项目类别:
Standard Grant