Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2020.56
URN: urn:nbn:de:0030-drops-134001
URL: https://drops.dagstuhl.de/opus/volltexte/2020/13400/
Huang, Xuangui
Space Hardness of Solving Structured Linear Systems
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{huang:LIPIcs:2020:13400,
author = {Xuangui Huang},
title = {{Space Hardness of Solving Structured Linear Systems}},
booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)},
pages = {56:1--56:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-173-3},
ISSN = {1868-8969},
year = {2020},
volume = {181},
editor = {Yixin Cao and Siu-Wing Cheng and Minming Li},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13400},
URN = {urn:nbn:de:0030-drops-134001},
doi = {10.4230/LIPIcs.ISAAC.2020.56},
annote = {Keywords: linear system solver, logarithmic space, threshold circuit}
}
| Keywords: | linear system solver, logarithmic space, threshold circuit | |
| Seminar: | 31st International Symposium on Algorithms and Computation (ISAAC 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 04.12.2020 |
