CRII: AF: Linear-Algebraic Pseudorandomness

CRII:AF:线性代数伪随机性

基本信息

  • 批准号:
    1755921
  • 负责人:
  • 金额:
    $ 17.5万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2018
  • 资助国家:
    美国
  • 起止时间:
    2018-02-01 至 2021-01-31
  • 项目状态:
    已结题

项目摘要

Error-resilient communication lies at the backbone of modern computer networks and storage systems. Such schemes have the property of being pseudorandom in that they are explicitly constructed without randomness (which can be important, such as for efficient decoding), and yet (almost) share the error-resilience afforded by truly-random communication protocols.  The construction and analysis of such schemes often uses linear algebra, and recently it has been shown that one can improve such schemes (in particular, list-decodable codes) by constructing certain pseudorandom linear-algebraic objects. Such linear-algebraic pseudorandom notions have turned out to be interesting independent of their coding-theoretic applications, as they mirror many well-studied notions in statistical (min-entropy) pseudorandomness, have applications to improving the time- and randomness-efficiency of linear-algebraic algorithms, and have connections to the polynomial method in mathematics.  This research will study the foundations of linear-algebraic pseudorandomness by attacking its main open problems, strengthening known connections, and discovering new connections. This project also has a broader impact through course design, organization of workshops, and training of undergraduate and graduate students.This project has two main focuses.  The first is on explicit constructions of linear-algebraic pseudorandom objects. In particular, this project studies rank extractors (a small collection of dimension-reducing linear maps that will preserve the dimension of a linear space on average), subspace-evasive sets (a large set which has small intersections with any small-dimensional linear space), and dimension expanders (a small collection of linear maps which increase the dimension of any small-dimensional linear space). While rank extractors and dimension expanders now have good constructions known, they lack optimality in several parameter regimes, and this project seeks to close these gaps, for example by tightening current analyses.  In contrast, all known explicit constructions of subspace-evasive sets are far from optimal, and this project seeks new avenues of construction.  Further, the project will explore the many relationships of these objects, such as with recent work on two-source (min-entropy) extractors, and known applications of expander graphs.The second focus on this project is on the polynomial method, a method in mathematics which has yielded dramatic solutions to problems in combinatorics and number theory.  It turns out that the linear-algebraic tools used in the analysis of the above pseudorandom objects has a natural phrasing in the language of the polynomial method. This project will sharpen these linear-algebraic tools to obtain new results via the polynomial method.
容错通信位于现代计算机网络和存储系统的主干上。这种方案具有伪随机性的性质,因为它们被显式地构造而没有随机性(这对于有效的译码来说可能是重要的),并且(几乎)共享真正随机通信协议所提供的差错恢复能力。这种方案的构造和分析通常使用线性代数,最近已经表明人们可以通过构造某些伪随机线性代数对象来改进这种方案(特别是列表可译码)。这种线性代数伪随机概念已经被证明是有趣的,与它们的编码理论应用无关,因为它们反映了统计(最小熵)伪随机性中许多研究得很好的概念,应用于提高线性代数算法的时间效率和随机性效率,并与数学中的多项式方法有关。本研究将通过攻击线性代数伪随机性的主要公开问题、加强已知联系和发现新的联系来研究线性代数伪随机性的基础。这个项目还通过课程设计、研讨会的组织以及本科生和研究生的培训产生了更广泛的影响。这个项目有两个主要的焦点。第一个是线性代数伪随机对象的显式构造。特别是,这个项目研究了秩萃取器(降维线性映射的一个小集合,它将平均保持线性空间的维度)、子空间回避集(与任何小维线性空间有小交集的大集合)和维扩张器(一个小的线性映射集合,它增加了任何小维线性空间的维度)。虽然秩抽取器和维度扩张器现在都有已知的良好结构,但它们在几个参数范围内缺乏最优性,本项目试图通过加强当前分析来弥合这些差距。相反,所有已知的子空间回避集合的显式构造都远不是最优的,本项目寻求新的构造途径。此外,该项目将探索这些对象的许多关系,例如最近关于两源(最小熵)萃取器的工作,以及已知的扩张器图的应用。本项目的第二个重点是多项式方法,数学中的一种方法,它对组合学和数论中的问题产生了戏剧性的解决方案。事实证明,用于分析上述伪随机对象的线性代数工具具有多项式方法的语言的自然语法。本项目将锐化这些线性代数工具,通过多项式方法获得新的结果。

项目成果

期刊论文数量(8)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Spatial Isolation Implies Zero Knowledge Even in a Quantum World
即使在量子世界中,空间隔离也意味着零知识
Algebraic Hardness Versus Randomness in Low Characteristic
低特性中的代数硬度与随机性
Random Restrictions and PRGs for PTFs in Gaussian Space
高斯空间中 PTF 的随机限制和 PRG
Towards blackbox identity testing of log-variate circuits
  • DOI:
    10.4230/lipics.icalp.2018.54
  • 发表时间:
    2018-07
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Michael A. Forbes;Sumanta K Ghosh;Nitin Saxena
  • 通讯作者:
    Michael A. Forbes;Sumanta K Ghosh;Nitin Saxena
An improved derandomization of the switching lemma
改进的切换引理去随机化
{{ 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 }}

Michael Forbes其他文献

Benders Decomposition with Delayed Disaggregation for the Active Passive Vehicle Routing Problem
主动被动车辆路径问题的延迟分解 Benders 分解
The Value of Drilling—A Chance-Constrained Optimization Approach
  • DOI:
    10.1007/s42461-024-01061-8
  • 发表时间:
    2024-08-22
  • 期刊:
  • 影响因子:
    2.000
  • 作者:
    Rick Jeuken;Michael Forbes
  • 通讯作者:
    Michael Forbes
Pupil-sparing third nerve palsies and hemiataxia: Claude’s and reverse Claude’s syndrome
  • DOI:
    10.1016/j.jocn.2015.12.010
  • 发表时间:
    2016-06-01
  • 期刊:
  • 影响因子:
  • 作者:
    James R. Bateman;Pavan Murty;Michael Forbes;Kisha Young Collier;Danoushka Tememe;Octavio de Marchena;William J. Powers
  • 通讯作者:
    William J. Powers
Augmentation of CFTR maturation by S-nitrosoglutathione reductase 1 2
S-亚硝基谷胱甘肽还原酶促进 CFTR 成熟 1 2
  • DOI:
  • 发表时间:
    2015
  • 期刊:
  • 影响因子:
    0
  • 作者:
    K. Zaman;Victoria Sawczak;Atiya Zaidi;Maya Butler;Deric Bennett;Paulina;Getsy;Maryam Zeinomar;Zivi Greenberg;Michael Forbes;Shagufta Rehman;Vinod;Jyothikumar;Kimberly Deronde;A. Sattar;Laura A. Smith;Deborah A. Corey;Adam;Straub;F. Sun;L. Palmer;A. Periasamy;S. Randell;T. Kelley;S. Lewis;B. Gaston
  • 通讯作者:
    B. Gaston
IN GOLF PUTTING Examining visual and attentional focus influences on golf putting performance using a dual-task paradigm
在高尔夫推杆中使用双任务范例检查视觉和注意力焦点对高尔夫推杆表现的影响
  • DOI:
  • 发表时间:
    2017
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Michael Forbes
  • 通讯作者:
    Michael Forbes

Michael Forbes的其他文献

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

{{ truncateString('Michael Forbes', 18)}}的其他基金

Compressible Turbulence from Quantum to Classical
从量子到经典的可压缩湍流
  • 批准号:
    2309322
  • 财政年份:
    2023
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Standard Grant
CAREER: Algebraic and Geometric Complexity Theory
职业:代数和几何复杂性理论
  • 批准号:
    2047310
  • 财政年份:
    2021
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Continuing Grant
Quantum Simulation of Turbulence with Cold Atoms
冷原子湍流的量子模拟
  • 批准号:
    2012190
  • 财政年份:
    2020
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Continuing Grant
AF: Small: Challenges in Unconditional Pseudorandomness for Boolean Computation
AF:小:布尔计算无条件伪随机性的挑战
  • 批准号:
    1814788
  • 财政年份:
    2018
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Standard Grant
Quantum Dynamics with Cold Atoms
冷原子的量子动力学
  • 批准号:
    1707691
  • 财政年份:
    2017
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Continuing Grant

相似国自然基金

基于前瞻性队列的双酚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 万元
  • 项目类别:
    青年科学基金项目

相似海外基金

AF: Small: RUI: Toward High-Performance Block Krylov Subspace Algorithms for Solving Large-Scale Linear Systems
AF:小:RUI:用于求解大规模线性系统的高性能块 Krylov 子空间算法
  • 批准号:
    2327619
  • 财政年份:
    2023
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Standard Grant
AF: Medium: Collaborative Research: Beyond Sparsity: Refined Measures of Complexity for Linear Algebra
AF:媒介:协作研究:超越稀疏性:线性代数复杂性的精确度量
  • 批准号:
    1763481
  • 财政年份:
    2018
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Continuing Grant
CCF-BSF: AF: Small: Collaborative Research: Practice-Friendly Theory and Algorithms for Linear Regression Problems
CCF-BSF:AF:小型:协作研究:线性回归问题的实用理论和算法
  • 批准号:
    1814041
  • 财政年份:
    2018
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Standard Grant
AF: Small: Data Stream Algorithms with Application to Linear Algebra
AF:小:数据流算法及其在线性代数中的应用
  • 批准号:
    1815840
  • 财政年份:
    2018
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Standard Grant
CCF-BSF: AF: Small: Collaborative Research: Practice-Friendly Theory and Algorithms for Linear Regression Problems
CCF-BSF:AF:小型:协作研究:线性回归问题的实用理论和算法
  • 批准号:
    1813374
  • 财政年份:
    2018
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Standard Grant
AF: Medium: Collaborative Research: Beyond Sparsity: Refined Measures of Complexity for Linear Algebra
AF:媒介:协作研究:超越稀疏性:线性代数复杂性的精确度量
  • 批准号:
    1763315
  • 财政年份:
    2018
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Continuing Grant
AF: Small: A-Hypergeometric Solutions of Linear Differential Equations
AF:小:线性微分方程的 A 超几何解
  • 批准号:
    1618657
  • 财政年份:
    2016
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Standard Grant
AF: Small: General Linear Multimethods for the Time Integration of Multiscale Multiphysics Problems
AF:小:多尺度多物理问题时间积分的通用线性多方法
  • 批准号:
    1613905
  • 财政年份:
    2016
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Standard Grant
AF: Small: Linear Algebra++ and applications to machine learning
AF:小:线性代数及其在机器学习中的应用
  • 批准号:
    1527371
  • 财政年份:
    2015
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Standard Grant
AF: Small: Linear and Polynomial Threshold Functions: Structural Analysis and Algorithmic Applications
AF:小:线性和多项式阈值函数:结构分析和算法应用
  • 批准号:
    1420349
  • 财政年份:
    2014
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了