On the computational complexity of betti numbers reductions from matrix rank
Edelsbrunner, Herbert
Parsa, Salman
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.
SIAM
2014
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
https://research-explorer.app.ist.ac.at/record/2177
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>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1137/1.9781611973402.11
info:eu-repo/semantics/closedAccess