2020/03/16 by Xuangui Huang, Huang, Xuangui
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Matrix Theory and Algorithms #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2003.06993
openalex publication_date 2020/03/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.