CRII: AF: Linear-Algebraic Pseudorandomness

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

• 批准号: 1755921
• 负责人: Michael Forbes
• 金额: $ 17.5万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-02-01 至 2021-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1755921&HistoricalAwards=false
• 关键词: CRII; AF; Linear; Algebraic; Pseudorandomness

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.

容错通信位于现代计算机网络和存储系统的主干上。这种方案具有伪随机性的性质，因为它们被显式地构造而没有随机性(这对于有效的译码来说可能是重要的)，并且(几乎)共享真正随机通信协议所提供的差错恢复能力。这种方案的构造和分析通常使用线性代数，最近已经表明人们可以通过构造某些伪随机线性代数对象来改进这种方案(特别是列表可译码)。这种线性代数伪随机概念已经被证明是有趣的，与它们的编码理论应用无关，因为它们反映了统计(最小熵)伪随机性中许多研究得很好的概念，应用于提高线性代数算法的时间效率和随机性效率，并与数学中的多项式方法有关。本研究将通过攻击线性代数伪随机性的主要公开问题、加强已知联系和发现新的联系来研究线性代数伪随机性的基础。这个项目还通过课程设计、研讨会的组织以及本科生和研究生的培训产生了更广泛的影响。这个项目有两个主要的焦点。第一个是线性代数伪随机对象的显式构造。特别是，这个项目研究了秩萃取器(降维线性映射的一个小集合，它将平均保持线性空间的维度)、子空间回避集(与任何小维线性空间有小交集的大集合)和维扩张器(一个小的线性映射集合，它增加了任何小维线性空间的维度)。虽然秩抽取器和维度扩张器现在都有已知的良好结构，但它们在几个参数范围内缺乏最优性，本项目试图通过加强当前分析来弥合这些差距。相反，所有已知的子空间回避集合的显式构造都远不是最优的，本项目寻求新的构造途径。此外，该项目将探索这些对象的许多关系，例如最近关于两源(最小熵)萃取器的工作，以及已知的扩张器图的应用。本项目的第二个重点是多项式方法，数学中的一种方法，它对组合学和数论中的问题产生了戏剧性的解决方案。事实证明，用于分析上述伪随机对象的线性代数工具具有多项式方法的语言的自然语法。本项目将锐化这些线性代数工具，通过多项式方法获得新的结果。

项目成果

Spatial Isolation Implies Zero Knowledge Even in a Quantum World

即使在量子世界中，空间隔离也意味着零知识

• DOI: 10.1109/focs.2018.00077
• 发表时间: 2018
• 期刊: 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2018
• 作者: Chiesa, Alessandro;Forbes, Michael A.;Gur, Tom;Spooner, Nicholas
• 通讯作者: Spooner, Nicholas

Algebraic Hardness Versus Randomness in Low Characteristic

低特性中的代数硬度与随机性

• 发表时间: 2020
• 期刊: Leibniz international proceedings in informatics
• 作者: Andrews, Robert

Random Restrictions and PRGs for PTFs in Gaussian Space

高斯空间中 PTF 的随机限制和 PRG

• 发表时间: 2022
• 期刊: Leibniz international proceedings in informatics
• 作者: Kelley, Zander;Meka, Raghu
• 通讯作者: Meka, Raghu

Towards blackbox identity testing of log-variate circuits

• DOI: 10.4230/lipics.icalp.2018.54
• 发表时间: 2018-07
• 作者: Michael A. Forbes;Sumanta K Ghosh;Nitin Saxena

An improved derandomization of the switching lemma

改进的切换引理去随机化

• DOI: 10.1145/3406325.3451054
• 发表时间: 2021
• 期刊: STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Kelley, Zander