Approximating Iterated Multiplication of Stochastic Matrices in Small Space
Approximating Iterated Multiplication of Stochastic Matrices in Small Space
复制标题
小空间中随机矩阵的近似迭代乘法
DOI：
10.1145/3564246.3585181
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
A. Ta
中科院分区：
文献类型：
--
作者：
Gil Cohen;Dean Doron;Ori Sberlo;A. Ta
矩阵幂，更一般的迭代矩阵乘法，是一个基本的线性代数原语，在计算机科学中有无数的应用。特别感兴趣的是问题的空间复杂性，因为它构成了解决BPL与L问题的主要途径。Saks和Zhou [JCSS '99]的开创性工作给出了在O（log 3/2n + logn·logw）空间中逼近n个w × w随机矩阵乘积的确定性算法。Saks-Zhou的第一个改进是由Hoza [RANDOM '21]实现的，他在n = poly（w）区域中给出了对数改进，达到了O（1/n loglogn·log3/2n）空间。我们给出了Saks和Zhou算法的第一个多项式改进。该算法的空间复杂度为O（logn + logn·logw）。特别是，在制度logn> log2 w，我们的算法运行在接近最优的O（logn）空间，提高了以前的最佳O（log3/2n）。为了获得我们的结果矩阵供电的特殊情况下，我们利用最近的机器从时间和空间有界的拉普拉斯求解器的萨克斯周框架，并设计一个复杂的精度交替递归计划。这使我们能够绕过每个递归级别都要支付日志空间的瓶颈。迭代矩阵乘法的一般情况下提出了几个额外的挑战，其中的实质是通过设计一个改进的移位和截断机制来处理。新的机制是可能的一种新的使用理查森迭代。
Matrix powering, and more generally iterated matrix multiplication, is a fundamental linear algebraic primitive with myriad applications in computer science. Of particular interest is the problem’s space complexity as it constitutes the main route towards resolving the BPL vs. L problem. The seminal work by Saks and Zhou [JCSS ’99] gives a deterministic algorithm for approximating the product of n stochastic matrices of dimension w × w in space O(log3/2n + √logn · logw). The first improvement upon Saks–Zhou was achieved by Hoza [RANDOM ’21] who gave a logarithmic improvement in the n=poly(w) regime, attaining O(1/√loglogn · log3/2n) space. We give the first polynomial improvement over Saks and Zhou’s algorithm. Our algorithm achieves space complexity of O(logn + √logn· logw). In particular, in the regime logn > log2 w, our algorithm runs in nearly-optimal O(logn) space, improving upon the previous best O(log3/2n). To obtain our result for the special case of matrix powering, we harness recent machinery from time- and space-bounded Laplacian solvers to the Saks–Zhou framework and devise an intricate precision-alternating recursive scheme. This enables us to bypass the bottleneck of paying logn-space per recursion level. The general case of iterated matrix multiplication poses several additional challenges, the substantial of which is handled by devising an improved shift and truncate mechanism. The new mechanism is made possible by a novel use of the Richardson iteration.
登录
查看更多内容
用于交错篡改和篡改组合的不可延展代码、提取器和秘密共享
DOI：
10.1007/978-3-030-64381-2_21
发表时间：
2020
期刊：
Cham
影响因子：
--
作者：
Chattopadhyay, Eshan;Li, Xin
通讯作者：
Li, Xin
用于以任意顺序读取一次的分支程序的伪随机生成器
DOI：
10.1109/focs.2018.00093
发表时间：
2018
期刊：
59th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2018
影响因子：
--
作者：
Forbes, Michael A.;Kelley, Zander
通讯作者：
Kelley, Zander
小空间随机游走的高精度估计
DOI：
10.1109/focs46700.2020.00123
发表时间：
2020
期刊：
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS
影响因子：
--
作者：
Ahmadinejad, AmirMahdi;Kelner, Jonathan;Murtagh, Jack;Peebles, John;Sidford, Aaron;Vadhan, Salil
通讯作者：
Vadhan, Salil
用于只读单调分支程序的伪随机生成器
DOI：
10.4230/lipics.approx/random.2021.58
发表时间：
2021
影响因子：
--
作者：
Doron, Dean;Meka, Raghu;Reingold, Omer;Tal, Avishay;Vadhan, Salil
通讯作者：
Vadhan, Salil
通过无限大小图中的查询实现随机游走的确定性逼近
DOI：
10.1137/1.9781611977066.5
发表时间：
2022
期刊：
Proceedings of the SIAM Symposium on Simplicity in Algorithms
影响因子：
--
作者：
Pyne, Edward;Vadhan, Salil
通讯作者：
Vadhan, Salil