2026-08-07T12:10:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13400 2024-03-06T10:51:53Z ddc:004 open_access

Space Hardness of Solving Structured Linear Systems Huang, Xuangui linear system solver logarithmic space threshold circuit Space-efficient Laplacian solvers are closely related to derandomization of space-bound randomized computations. 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 used to solve all linear systems with similar space complexity. Previously Kyng and Zhang [Rasmus Kyng and Peng Zhang, 2017] proved such 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xuangui Huang 2020 Is Part Of LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2020.56 urn:nbn:de:0030-drops-134001 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.56 eng https://creativecommons.org/licenses/by/3.0/legalcode