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.

错误的通信位于现代计算机网络和存储系统的骨干上。这样的方案具有伪随机的属性，因为它们是在没有随机性的情况下明确构造的（这可能很重要，例如对于有效的解码），并且（几乎）共享由真正的随机通信协议提供的错误弹性。此类方案的构建和分析通常使用线性代数，最近已经表明，可以通过构造某些伪和线性的代码对象来改善此类方案（尤其是可列表对代码）。 Such linear-algebraic pseudorandom notions have turned out to be interesting independent of their coding-theoretic applications, as they mirror many well-studied notes in statistical (min-entropy) pseudorandomness, have applications to improve the time- and randomness-efficiency of linear-algebraic algorithms, and have connections to the polynomial method in mathematics.这项研究将通过攻击其主要的开放问题，加强已知的联系并发现新的联系，研究线性 - 地球化伪随机的基础。该项目还通过课程设计，研讨会的组织以及对本科和研究生的培训产生了更大的影响。该项目有两个主要重点。首先是在线性偏格伪界对象的显式结构上。 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).尽管等级提取器和维度扩展器现在已经知道了良好的结构，但相比之下，它们缺乏最佳性，但所有已知的显式构造构造远非最佳，并且该项目寻求新的构建途径。此外，该项目将探索这些对象的许多关系，例如最近在两种源（最小内侧）提取器上的工作以及扩展器图的已知应用。该项目的第二个重点是多项式方法，这是一种数学方法，这是对组合术和数字理论中问题的戏剧化解决方案。事实证明，用于分析上述伪随机对象的线性代数工具具有多项式方法语言的自然措辞。该项目将锐化这些线性地球工具，以通过多项式方法获得新的结果。

项目成果

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

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

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