AF: Small: Understanding Expansion Phenomena: Graphical, Hypergraphical, Geometric, and Quantum

AF:小:理解膨胀现象:图形、超图形、几何和量子

基本信息

  • 批准号:
    2326685
  • 负责人:
  • 金额:
    $ 20.22万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2023
  • 资助国家:
    美国
  • 起止时间:
    2023-10-01 至 2025-09-30
  • 项目状态:
    未结题

项目摘要

A broad variety of phenomena in computation can be viewed as different forms of “expansion”, which ensure that local properties which can be observed by looking at small parts of an object, can be used to influence and understand global properties exhibited at a much larger scale. This is an important design requirement in several applications, such as (1) classical and quantum error-correction, where one wants errors to be easily detectable by local checks, (2) optimization problems, where one wants local choices to push the global solution towards optimality, and (3) geometric embeddings of high-dimensional data, where one wants to use local (low-dimensional) conditions to influence high-dimensional behavior. In the past few years, several new concepts and techniques have emerged to study expansion phenomena in different contexts. This project aims to study several different forms of expansion phenomena in a unified way, with an emphasis on applications in the areas of error-correcting codes and (approximate) optimization. This research is likely to lead to new connections between multiple areas where such phenomena are useful. The material generated as part of this research will also be disseminated through surveys and a series of expository videos. This project aims to obtain a unified view of the following different forms and applications of expansion phenomena:- Classical notions of graph expansion and novel notions of high-dimensional expansion for hypergraphs, and their connections to recent advances in coding theory.- Applications of classical expansion phenomena to quantum codes, as well as quantum extensions of classical expansion phenomena.- Connections of high-dimensional expansion to the study and approximability of expansion phenomena in geometric spaces, and related problems about fine-grained graph expansion.The research directions pursued in this project aim to introduce new techniques in algorithmic coding theory and in the study of approximability of discrete and continuous optimization problems. The project considers several problems that have proved to be bottlenecks for current algorithmic and analytic techniques, explores new approaches arising from the study of expansion in a different context. The project aims to apply these ideas for the design of new error-correcting codes, and new algorithms for existing codes, towards the design of new pseudorandom objects, and also new families of combinatorial and geometric instances for proving inapproximability results.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.
计算中的各种各样的现象可以被视为不同形式的“扩展”,这确保了可以通过观察对象的小部分来观察的局部属性可以用来影响和理解在更大尺度上表现出的全局属性。这在若干应用中是重要的设计要求,例如(1)经典和量子纠错,其中人们希望通过局部检查容易地检测到错误,(2)优化问题,其中人们希望局部选择将全局解推向最优,以及(3)高维数据的几何嵌入,其中想要使用局部(低维)条件来影响高维行为。在过去的几年里,出现了一些新的概念和技术来研究不同背景下的膨胀现象。该项目旨在以统一的方式研究几种不同形式的膨胀现象,重点是纠错码和(近似)优化领域的应用。这项研究可能会导致多个领域之间的新联系,这些现象是有用的。作为这项研究的一部分而产生的材料也将通过调查和一系列的临时录像来传播。该项目旨在获得以下不同形式和扩展现象应用的统一观点:-图扩展的经典概念和超图高维扩展的新概念,以及它们与编码理论最新进展的联系。 经典膨胀现象在量子码中的应用,以及经典膨胀现象的量子扩展。 高维扩展与几何空间中扩展现象的研究和可逼近性的联系,以及细粒度图扩展的相关问题。本项目的研究方向旨在引入算法编码理论和离散和连续优化问题的可逼近性研究中的新技术。该项目考虑了已被证明是当前算法和分析技术瓶颈的几个问题,探索了在不同背景下研究扩展所产生的新方法。该项目旨在将这些想法应用于新的纠错码的设计,以及现有代码的新算法,用于新的伪随机对象的设计,以及用于证明不可逼近性结果的组合和几何实例的新家族。该奖项反映了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 }}

Madhur Tulsiani其他文献

Algorithms and hardness for subspace approximation
子空间近似的算法和难度
  • DOI:
    10.1137/1.9781611973082.39
  • 发表时间:
    2009
  • 期刊:
  • 影响因子:
    0
  • 作者:
    A. Deshpande;Madhur Tulsiani;Nisheeth K. Vishnoi
  • 通讯作者:
    Nisheeth K. Vishnoi
Improved Pseudorandom Generators for Depth 2 Circuits
改进的深度 2 电路伪随机发生器
A characterization of strong approximation resistance
强逼近电阻的表征
Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution
规律性、增强和有效模拟每个高熵分布
Time Space Tradeoffs for Attacks against One-Way Functions and PRGs
针对单向函数和 PRG 的攻击的时空权衡

Madhur Tulsiani的其他文献

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

{{ truncateString('Madhur Tulsiani', 18)}}的其他基金

AF: Small: Parallels in Approximability of Discrete and Continuous Optimization Problems
AF:小:离散和连续优化问题的近似性的相似性
  • 批准号:
    1816372
  • 财政年份:
    2018
  • 资助金额:
    $ 20.22万
  • 项目类别:
    Standard Grant
CAREER: Understanding Polynomial Structure Analytically and Algorithmically
职业:通过分析和算法理解多项式结构
  • 批准号:
    1254044
  • 财政年份:
    2013
  • 资助金额:
    $ 20.22万
  • 项目类别:
    Continuing 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 RNAs在克罗恩病发生发展中的功能和作用机制
  • 批准号:
    31870821
  • 批准年份:
    2018
  • 资助金额:
    56.0 万元
  • 项目类别:
    面上项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
  • 批准号:
    31802058
  • 批准年份:
    2018
  • 资助金额:
    26.0 万元
  • 项目类别:
    青年科学基金项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
  • 批准号:
    31772128
  • 批准年份:
    2017
  • 资助金额:
    60.0 万元
  • 项目类别:
    面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
  • 批准号:
    81704176
  • 批准年份:
    2017
  • 资助金额:
    20.0 万元
  • 项目类别:
    青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
  • 批准号:
    91640114
  • 批准年份:
    2016
  • 资助金额:
    85.0 万元
  • 项目类别:
    重大研究计划

相似海外基金

SaTC: CORE: Small: NSF-DST: Understanding Network Structure and Communication for Supporting Information Authenticity
SaTC:核心:小型:NSF-DST:了解支持信息真实性的网络结构和通信
  • 批准号:
    2343387
  • 财政年份:
    2024
  • 资助金额:
    $ 20.22万
  • 项目类别:
    Standard Grant
CAREER: Understanding the Dynamic Mechanical Adaptations of Bone Tissue at Small Length Scales
职业:了解小长度尺度下骨组织的动态机械适应
  • 批准号:
    2339836
  • 财政年份:
    2024
  • 资助金额:
    $ 20.22万
  • 项目类别:
    Standard Grant
RI: Small: Understanding Hand Interaction In The Jumble of Internet Videos
RI:小:在混乱的互联网视频中理解手部交互
  • 批准号:
    2426592
  • 财政年份:
    2024
  • 资助金额:
    $ 20.22万
  • 项目类别:
    Standard Grant
Collaborative Research: RI: Small: Motion Fields Understanding for Enhanced Long-Range Imaging
合作研究:RI:小型:增强远程成像的运动场理解
  • 批准号:
    2232298
  • 财政年份:
    2023
  • 资助金额:
    $ 20.22万
  • 项目类别:
    Standard Grant
Collaborative Research: SaTC: CORE: Small: Understanding the Limitations of Wireless Network Security Designs Leveraging Wireless Properties: New Threats and Defenses in Practice
协作研究:SaTC:核心:小型:了解利用无线特性的无线网络安全设计的局限性:实践中的新威胁和防御
  • 批准号:
    2316720
  • 财政年份:
    2023
  • 资助金额:
    $ 20.22万
  • 项目类别:
    Standard Grant
Understanding prokaryotic small proteins from context
从背景理解原核小蛋白
  • 批准号:
    FT230100724
  • 财政年份:
    2023
  • 资助金额:
    $ 20.22万
  • 项目类别:
    ARC Future Fellowships
Collaborative Research: HCC: Small: Understanding Online-to-Offline Sexual Violence through Data Donation from Users
合作研究:HCC:小型:通过用户捐赠的数据了解线上线下性暴力
  • 批准号:
    2401775
  • 财政年份:
    2023
  • 资助金额:
    $ 20.22万
  • 项目类别:
    Standard Grant
Collaborative Research: SaTC: CORE: Small: Understanding and Taming Deterministic Model Bit Flip attacks in Deep Neural Networks
协作研究:SaTC:核心:小型:理解和驯服深度神经网络中的确定性模型位翻转攻击
  • 批准号:
    2342618
  • 财政年份:
    2023
  • 资助金额:
    $ 20.22万
  • 项目类别:
    Standard Grant
Collaborative Research: NSF-CSIRO: HCC: Small: Understanding Bias in AI Models for the Prediction of Infectious Disease Spread
合作研究:NSF-CSIRO:HCC:小型:了解预测传染病传播的 AI 模型中的偏差
  • 批准号:
    2302969
  • 财政年份:
    2023
  • 资助金额:
    $ 20.22万
  • 项目类别:
    Standard Grant
Understanding interactions between minerals and small biopolymers under extreme conditions
了解极端条件下矿物质和小型生物聚合物之间的相互作用
  • 批准号:
    2870997
  • 财政年份:
    2023
  • 资助金额:
    $ 20.22万
  • 项目类别:
    Studentship
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了