论文标题
解决结构化线性系统的空间硬度
Space Hardness of Solving Structured Linear Systems
论文作者
论文摘要
我们表明，如果可以扩展无向Laplacian矩阵的概率对数空间求解器或确定性的接近对数空间求解器，以求解线性系统的稍大较大的子类，则可以使用它们来求解具有相似空间复杂性的所有线性系统。以前，Kyng和Zhang使用近似求解器之间的减少在时间复杂度设置中证明了相似的结果。我们证明可以使用恒定深度，多项式大小的阈值电路来实施它们的减少。
We show that if the probabilistic logarithmic-space solver or the deterministic nearly logarithmic-space solver for undirected Laplacian matrices can be extended to solve slightly larger subclasses of linear systems, then they can be use to solve all linear systems with similar space complexity. Previously Kyng and Zhang proved similar results in the time complexity setting using reductions between approximate solvers. We prove that their reductions can be implemented using constant-depth, polynomial-size threshold circuits.
