[{"author":[{"last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","first_name":"Herbert"},{"id":"4BDBD4F2-F248-11E8-B48F-1D18A9856A87","full_name":"Parsa, Salman","first_name":"Salman","last_name":"Parsa"}],"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."}],"date_created":"2018-12-11T11:56:09Z","doi":"10.1137/1.9781611973402.11","publication_status":"published","oa_version":"None","conference":{"name":"SODA: Symposium on Discrete Algorithms","start_date":"2014-01-05","location":"Portland, USA","end_date":"2014-01-07"},"quality_controlled":"1","citation":{"short":"H. Edelsbrunner, S. Parsa, in:, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2014, pp. 152–160.","ama":"Edelsbrunner H, Parsa S. On the computational complexity of betti numbers reductions from matrix rank. In: <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>. SIAM; 2014:152-160. doi:<a href=\"https://doi.org/10.1137/1.9781611973402.11\">10.1137/1.9781611973402.11</a>","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.","ieee":"H. Edelsbrunner and S. Parsa, “On the computational complexity of betti numbers reductions from matrix rank,” in <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Portland, USA, 2014, pp. 152–160.","chicago":"Edelsbrunner, Herbert, and Salman Parsa. “On the Computational Complexity of Betti Numbers Reductions from Matrix Rank.” In <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 152–60. SIAM, 2014. <a href=\"https://doi.org/10.1137/1.9781611973402.11\">https://doi.org/10.1137/1.9781611973402.11</a>.","apa":"Edelsbrunner, H., &#38; Parsa, S. (2014). On the computational complexity of betti numbers reductions from matrix rank. In <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 152–160). Portland, USA: SIAM. <a href=\"https://doi.org/10.1137/1.9781611973402.11\">https://doi.org/10.1137/1.9781611973402.11</a>","mla":"Edelsbrunner, Herbert, and Salman Parsa. “On the Computational Complexity of Betti Numbers Reductions from Matrix Rank.” <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, SIAM, 2014, pp. 152–60, doi:<a href=\"https://doi.org/10.1137/1.9781611973402.11\">10.1137/1.9781611973402.11</a>."},"publication":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms","department":[{"_id":"HeEd"}],"publist_id":"4805","language":[{"iso":"eng"}],"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","corr_author":"1","year":"2014","status":"public","type":"conference","date_published":"2014-01-01T00:00:00Z","page":"152 - 160","month":"01","publisher":"SIAM","fulldoi":"https://doi.org/10.1137/1.9781611973402.11","date_updated":"2024-10-09T20:55:33Z","_id":"2177","day":"01","title":"On the computational complexity of betti numbers reductions from matrix rank","scopus_import":1}]