Average complexity of matrix reduction for clique filtrations

We study the algorithmic complexity of computing persistent homology of a randomly chosen filtration. Specifically, we prove upper bounds for the average fill-up (number of non-zero entries) of the boundary matrix on Erd\"os-Renyi filtrations and Vietoris-Rips filtration after matrix reduction. Our bounds show that, in both cases, the reduced matrix is expected to be significantly sparser than what the general worst-case predicts. Our bounds are based on previous results on the expected first Betti numbers of corresponding complexes. We establish a link between these results to the fill-up of the boundary matrix. Our bound forVietoris-Rips complexes is asymptotically tight up to logarithmic factors