Document Open Access Logo

Space Hardness of Solving Structured Linear Systems

Author Xuangui Huang

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2020.56.pdf
  • Filesize: 0.59 MB
  • 12 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • linear system solver
  • logarithmic space
  • threshold circuit

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Xuangui Huang. Space Hardness of Solving Structured Linear Systems. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 56:1-56:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ISAAC.2020.56

Author Details

Xuangui Huang
  • Northeastern University, Boston, MA, USA

Funding

Supported by NSF CCF award 1813930.

Acknowledgements

The author thanks Emanuele Viola for helpful discussions, and anonymous reviewers for comments.

References

  1. AmirMahdi Ahmadinejad, Jonathan A. Kelner, Jack Murtagh, John Peebles, Aaron Sidford, and Salil P. Vadhan. High-precision estimation of random walks in small space. CoRR, abs/1912.04524, 2019. URL: http://arxiv.org/abs/1912.04524.
  2. Eric Allender, Robert Beals, and Mitsunori Ogihara. The complexity of matrix rank and feasible systems of linear equations. Comput. Complex., 8(2):99-126, 1999. URL: https://doi.org/10.1007/s000370050023.
  3. Sanjeev Arora and Boaz Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009. URL: http://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521424264.
  4. Allan Borodin. On relating time and space to size and depth. SIAM Journal on Computing, 6(4):733-744, 1977. URL: https://doi.org/10.1137/0206054.
  5. Peter Clote and Evangelos Kranakis. Boolean Functions and Computation Models. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2002. URL: https://doi.org/10.1007/978-3-662-04943-3.
  6. Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao, and Shen Chen Xu. Solving SDD linear systems in nearly mlog^1/2n time. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 343-352, 2014. URL: https://doi.org/10.1145/2591796.2591833.
  7. Dean Doron, François Le Gall, and Amnon Ta-Shma. Probabilistic logarithmic-space algorithms for laplacian solvers. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2017, August 16-18, 2017, Berkeley, CA, USA, pages 41:1-41:20, 2017. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.41.
  8. Dean Doron, Jack Murtagh, Salil P. Vadhan, and David Zuckerman. Spectral sparsification via bounded-independence sampling. Electronic Colloquium on Computational Complexity (ECCC), 27:26, 2020. URL: https://eccc.weizmann.ac.il/report/2020/026.
  9. François Le Gall. Powers of tensors and fast matrix multiplication. In International Symposium on Symbolic and Algebraic Computation, ISSAC '14, Kobe, Japan, July 23-25, 2014, pages 296-303, 2014. URL: https://doi.org/10.1145/2608628.2608664.
  10. William Hesse, Eric Allender, and David A. Mix Barrington. Uniform constant-depth threshold circuits for division and iterated multiplication. J. Comput. Syst. Sci., 65(4):695-716, 2002. URL: https://doi.org/10.1016/S0022-0000(02)00025-9.
  11. Neil Immerman and Susan Landau. The complexity of iterated multiplication. In Proceedings: Fourth Annual Structure in Complexity Theory Conference, University of Oregon, Eugene, Oregon, USA, June 19-22, 1989, pages 104-111, 1989. URL: https://doi.org/10.1109/SCT.1989.41816.
  12. Rasmus Kyng and Peng Zhang. Hardness results for structured linear systems. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 684-695, 2017. Google Scholar
  13. Rasmus Kyng and Peng Zhang. Hardness results for structured linear systems. CoRR, abs/1705.02944, 2017. URL: http://arxiv.org/abs/1705.02944.
  14. Alexis Maciel and Denis Thérien. Efficient threshold circuits for power series. Inf. Comput., 152(1):62-73, 1999. URL: https://doi.org/10.1006/inco.1998.2783.
  15. Jack Murtagh, Omer Reingold, Aaron Sidford, and Salil P. Vadhan. Derandomization beyond connectivity: Undirected laplacian systems in nearly logarithmic space. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 801-812, 2017. URL: https://doi.org/10.1109/FOCS.2017.79.
  16. John H. Reif and Stephen R. Tate. On threshold circuits and polynomial computation. SIAM J. Comput., 21(5):896-908, 1992. URL: https://doi.org/10.1137/0221053.
  17. Omer Reingold, Luca Trevisan, and Salil P. Vadhan. Pseudorandom walks on regular digraphs and the RL vs. L problem. In Jon M. Kleinberg, editor, Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pages 457-466. ACM, 2006. URL: https://doi.org/10.1145/1132516.1132583.
  18. Michael E. Saks. Randomization and derandomization in space_bounded computation. In Steven Homer and Jin-Yi Cai, editors, Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, Philadelphia, Pennsylvania, USA, May 24-27, 1996, pages 128-149. IEEE Computer Society, 1996. URL: https://doi.org/10.1109/CCC.1996.507676.
  19. Michael E. Saks and Shiyu Zhou. RSPACE(S) backslashsubseteq dspace(s^3/2). In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995, pages 344-353, 1995. URL: https://doi.org/10.1109/SFCS.1995.492490.
  20. Daniel A. Spielman and Shang-Hua Teng. Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. SIAM J. Matrix Analysis Applications, 35(3):835-885, 2014. URL: https://doi.org/10.1137/090771430.
  21. Amnon Ta-Shma. Inverting well conditioned matrices in quantum logspace. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 881-890, 2013. URL: https://doi.org/10.1145/2488608.2488720.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact