--- _id: '2177' abstract: - lang: eng text: 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. author: - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Salman full_name: Parsa, Salman id: 4BDBD4F2-F248-11E8-B48F-1D18A9856A87 last_name: Parsa citation: ama: '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' apa: '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' chicago: 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. ieee: 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. ista: '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.' mla: 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. short: H. Edelsbrunner, S. Parsa, in:, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2014, pp. 152–160. conference: end_date: 2014-01-07 location: Portland, USA name: 'SODA: Symposium on Discrete Algorithms' start_date: 2014-01-05 date_created: 2018-12-11T11:56:09Z date_published: 2014-01-01T00:00:00Z date_updated: 2021-01-12T06:55:48Z day: '01' department: - _id: HeEd doi: 10.1137/1.9781611973402.11 language: - iso: eng month: '01' oa_version: None page: 152 - 160 publication: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms publication_status: published publisher: SIAM publist_id: '4805' quality_controlled: '1' scopus_import: 1 status: public title: On the computational complexity of betti numbers reductions from matrix rank type: conference user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87 year: '2014' ...