---
_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: <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>'
  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>'
  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>.
  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.
  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.” <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>.
  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
corr_author: '1'
date_created: 2018-12-11T11:56:09Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2024-10-09T20:55:33Z
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'
...