CRII: AF: Applications of Spectral Sensitivity to Query and Communication Complexity

CRII:AF:频谱敏感性在查询和通信复杂性中的应用

基本信息

  • 批准号:
    2348489
  • 负责人:
  • 金额:
    $ 17.46万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2024
  • 资助国家:
    美国
  • 起止时间:
    2024-04-01 至 2026-03-31
  • 项目状态:
    未结题

项目摘要

The goal of this project is to help advance query complexity, a subfield of theoretical computer science that measures a computer program’s efficiency by the fraction of the input that is read. As an example, consider the problem of searching for an item in a list - an efficient program could potentially find the item quickly, and thus it is no longer necessary to read the rest of the input. The main tool used in this project will be a quantity called spectral sensitivity, which has recently been used in several major advances in query complexity. Query complexity has been a useful tool in helping understand the answers to questions such as to what extent access to randomness or quantum computers can make computer programs more efficient. This project aims to contribute to the answers to these and related questions within query complexity by using spectral sensitivity in novel ways. In addition, this project will fund undergraduate and graduate student researchers, and also continue to develop opportunities to study theoretical computer science at Portland State University.In particular, this project considers three areas. The first considers relationships between block sensitivity and sensitivity, and between sensitivity and degree. These are complexity measures that are useful in understanding the different models of query complexity including deterministic, randomized, and quantum. The second considers the query complexity of the composition of functions, which can reveal how the value of complexity measures can change when functions are combined. Finally, the project will also consider the communication complexity of certain classes of functions. In some cases, it is possible to relate the communication complexity of such functions to the query complexity of other functions, and to borrow techniques from query complexity.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.
这个项目的目标是帮助提高查询复杂性,这是理论计算机科学的一个子领域,它通过读取的输入的分数来衡量计算机程序的效率。例如,考虑在列表中搜索一个项目的问题-一个有效的程序可能会快速找到该项目,因此不再需要读取输入的其余部分。在这个项目中使用的主要工具将是一个称为光谱灵敏度的量,它最近已被用于查询复杂性的几个主要进展。查询复杂度是一个有用的工具,可以帮助理解一些问题的答案,比如在多大程度上访问随机性或量子计算机可以使计算机程序更有效。该项目旨在通过以新颖的方式使用光谱敏感性来回答这些问题以及查询复杂性中的相关问题。此外,该项目将资助本科生和研究生研究人员,也将继续开发在波特兰州立大学学习理论计算机科学的机会,特别是,该项目考虑三个领域。第一个考虑块灵敏度和灵敏度之间的关系,以及灵敏度和度之间的关系。这些复杂性度量有助于理解查询复杂性的不同模型,包括确定性、随机性和量子性。 第二种方法考虑函数组合的查询复杂度,它可以揭示函数组合时复杂度度量的值如何变化。最后,该项目还将考虑某些类函数的通信复杂性。在某些情况下,可以将这些功能的通信复杂性与其他功能的查询复杂性联系起来,并从查询复杂性中借用技术。该奖项反映了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 }}

Shravas Rao其他文献

Improved Lower Bounds for the Restricted Isometry Property of Subsampled Fourier Matrices
子采样傅里叶矩阵受限等距性质的改进下界
  • DOI:
  • 发表时间:
    2019
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Shravas Rao
  • 通讯作者:
    Shravas Rao
Optimal RIP Matrices with Slightly Less Randomness
随机性稍低的最优 RIP 矩阵
  • DOI:
  • 发表时间:
    2023
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Shravas Rao
  • 通讯作者:
    Shravas Rao
On Lipschitz Bijections Between Boolean Functions
关于布尔函数之间的 Lipschitz 双射
A Hoeffding inequality for Markov chains
马尔可夫链的 Hoeffding 不等式
The Fourier Transform of Restrictions of Functions on the Slice
切片上函数限制的傅里叶变换
  • DOI:
  • 发表时间:
    2021
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Shravas Rao
  • 通讯作者:
    Shravas Rao

Shravas Rao的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

相似国自然基金

基于前瞻性队列的双酚AF联合果糖加重代谢损伤的靶向代谢组学研究
  • 批准号:
    2025JJ30049
  • 批准年份:
    2025
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
U2AF2-circMMP1信号轴促进结直肠癌进展的分子机制研究
  • 批准号:
    2025JJ80723
  • 批准年份:
    2025
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
U2AF2精氯酸甲基化调控RNA转录合成在MTAP缺失骨肉瘤T细胞耗竭中的机制研究
  • 批准号:
  • 批准年份:
    2024
  • 资助金额:
    0 万元
  • 项目类别:
    青年科学基金项目
BDA-366通过MYD88/NF-κB/PGC1β通路杀伤 KMT2A/AF9 AML细胞的机制研究
  • 批准号:
  • 批准年份:
    2024
  • 资助金额:
    15.0 万元
  • 项目类别:
    省市级项目
Lu AF21934减少缺血性脑卒中导致的神经损伤的机制研究
  • 批准号:
  • 批准年份:
    2024
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
H2S介导剪接因子BraU2AF65a的S-巯基化修饰促进大白菜开花的分子机制
  • 批准号:
    32372727
  • 批准年份:
    2023
  • 资助金额:
    50 万元
  • 项目类别:
    面上项目
AF9通过ARRB2-MRGPRB2介导肠固有肥大细胞活化促进重症急性胰腺炎发生MOF的研究
  • 批准号:
    82300739
  • 批准年份:
    2023
  • 资助金额:
    30 万元
  • 项目类别:
    青年科学基金项目
剪接因子U2AF1突变在急性髓系白血病原发耐药中的机制研究
  • 批准号:
    82370157
  • 批准年份:
    2023
  • 资助金额:
    49 万元
  • 项目类别:
    面上项目
线粒体活性氧介导的胎盘早衰在孕期双酚AF暴露致婴幼儿神经发育迟缓中的作用
  • 批准号:
    82304160
  • 批准年份:
    2023
  • 资助金额:
    30 万元
  • 项目类别:
    青年科学基金项目
U2AF2-circMMP1调控能量代谢促进结直肠癌肝转移的分子机制
  • 批准号:
    82303789
  • 批准年份:
    2023
  • 资助金额:
    30 万元
  • 项目类别:
    青年科学基金项目

相似海外基金

Collaborative Research: AF: Medium: Polynomial Optimization: Algorithms, Certificates and Applications
合作研究:AF:媒介:多项式优化:算法、证书和应用
  • 批准号:
    2211972
  • 财政年份:
    2022
  • 资助金额:
    $ 17.46万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: Polynomial Optimization: Algorithms, Certificates and Applications
合作研究:AF:媒介:多项式优化:算法、证书和应用
  • 批准号:
    2211971
  • 财政年份:
    2022
  • 资助金额:
    $ 17.46万
  • 项目类别:
    Continuing Grant
CRII: AF: Optimization and sampling algorithms with provable generalization and runtime guarantees, with applications to deep learning
CRII:AF:具有可证明的泛化性和运行时保证的优化和采样算法,以及深度学习的应用
  • 批准号:
    2104528
  • 财政年份:
    2021
  • 资助金额:
    $ 17.46万
  • 项目类别:
    Standard Grant
AF: Small: Quantum Computational Pseudorandomness with Applications
AF:小:量子计算伪随机性及其应用
  • 批准号:
    2041841
  • 财政年份:
    2020
  • 资助金额:
    $ 17.46万
  • 项目类别:
    Standard Grant
AF: Small: Threshold Functions--Derandomization, Testing and Applications
AF:小:阈值函数——去随机化、测试和应用
  • 批准号:
    1910534
  • 财政年份:
    2020
  • 资助金额:
    $ 17.46万
  • 项目类别:
    Standard Grant
AF: Small: Quantum Computational Pseudorandomness with Applications
AF:小:量子计算伪随机性及其应用
  • 批准号:
    1921047
  • 财政年份:
    2018
  • 资助金额:
    $ 17.46万
  • 项目类别:
    Standard Grant
AF: Small: Toward Applications and Verification of Early Quantum Computers
AF:小:迈向早期量子计算机的应用和验证
  • 批准号:
    1813814
  • 财政年份:
    2018
  • 资助金额:
    $ 17.46万
  • 项目类别:
    Standard Grant
AF: Small: Collaborative Research: Certification for Semi-Algebraic Sets with Applications
AF:小:协作研究:半代数集及其应用的认证
  • 批准号:
    1812746
  • 财政年份:
    2018
  • 资助金额:
    $ 17.46万
  • 项目类别:
    Standard Grant
AF: Small: Quantum Computational Pseudorandomness with Applications
AF:小:量子计算伪随机性及其应用
  • 批准号:
    1816869
  • 财政年份:
    2018
  • 资助金额:
    $ 17.46万
  • 项目类别:
    Standard Grant
CRII: AF: Strongly Polynomial Algorithms for Market Equilibria with Applications to Network Flows and Nash Social Welfare
CRII:AF:市场均衡的强多项式算法及其在网络流量和纳什社会福利中的应用
  • 批准号:
    1755619
  • 财政年份:
    2018
  • 资助金额:
    $ 17.46万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了