# A (simple) classical algorithm for estimating Betti numbers

arXiv: https://arxiv.org/abs/2211.09618 · HTML: https://mlsanity.com/paper/2211.09618/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Nov 2022.

## Built on by (most cited first, 3 of 3)

- [MANTRA: The Manifold Triangulations Assemblage](https://mlsanity.com/paper/2410.02392/) (2024)
- [Provable quantum speedups for computing persistence in topological data analysis](https://mlsanity.com/paper/2410.21258/) (2024)
- [Combinatorial Multi-armed Bandits: Arm Selection via Group Testing](https://mlsanity.com/paper/2410.10679/) (2024)

## Abstract (arXiv)

We describe a simple algorithm for estimating the k-th normalized Betti number of a simplicial complex over n elements using the path integral Monte Carlo method. For a general simplicial complex, the running time of our algorithm is n^Oleft(frac1√γlogfrac1varepsilonright) with γ measuring the spectral gap of the combinatorial Laplacian and varepsilon ∈ (0,1) the additive precision. In the case of a clique complex, the running time of our algorithm improves to left(n/λmaxright)^Oleft(frac1√γlogfrac1varepsilonright) with λmax ≥ k, where λmax is the maximum eigenvalue of the combinatorial Laplacian. Our algorithm provides a classical benchmark for a line of quantum algorithms for estimating Betti numbers. On clique complexes it matches their running time when, for example, γ ∈ Omega(1) and k ∈ Omega(n).