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