On the computational complexity of betti numbers reductions from matrix rank
Edelsbrunner H, Parsa S. 2014. On the computational complexity of betti numbers reductions from matrix rank. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 152–160.
Download
No fulltext has been uploaded. References only!
Conference Paper
| Published
| English
Scopus indexed
Department
Abstract
We give evidence for the difficulty of computing Betti numbers of simplicial complexes over a finite field. We do this by reducing the rank computation for sparse matrices with to non-zero entries to computing Betti numbers of simplicial complexes consisting of at most a constant times to simplices. Together with the known reduction in the other direction, this implies that the two problems have the same computational complexity.
Publishing Year
Date Published
2014-01-01
Proceedings Title
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Page
152 - 160
Conference
SODA: Symposium on Discrete Algorithms
Conference Location
Portland, USA
Conference Date
2014-01-05 – 2014-01-07
IST-REx-ID
Cite this
Edelsbrunner H, Parsa S. On the computational complexity of betti numbers reductions from matrix rank. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM; 2014:152-160. doi:10.1137/1.9781611973402.11
Edelsbrunner, H., & Parsa, S. (2014). On the computational complexity of betti numbers reductions from matrix rank. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 152–160). Portland, USA: SIAM. https://doi.org/10.1137/1.9781611973402.11
Edelsbrunner, Herbert, and Salman Parsa. “On the Computational Complexity of Betti Numbers Reductions from Matrix Rank.” In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 152–60. SIAM, 2014. https://doi.org/10.1137/1.9781611973402.11.
H. Edelsbrunner and S. Parsa, “On the computational complexity of betti numbers reductions from matrix rank,” in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Portland, USA, 2014, pp. 152–160.
Edelsbrunner H, Parsa S. 2014. On the computational complexity of betti numbers reductions from matrix rank. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 152–160.
Edelsbrunner, Herbert, and Salman Parsa. “On the Computational Complexity of Betti Numbers Reductions from Matrix Rank.” Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2014, pp. 152–60, doi:10.1137/1.9781611973402.11.
Google Scholar