# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Zigzag Persistent Homology in Matrix Multiplication Time

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Milosavljevic, N., Morozov, D., & Skraba, P. (2011). Zigzag Persistent Homology
in Matrix Multiplication Time. In *Proceedings of the 27th Annual Symposium on Computational Geometry
(SCG'11)* (pp. 216-225). New York, NY: ACM. doi:10.1145/1998196.1998229.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0010-12C6-B

##### Abstract

We present a new algorithm for computing zigzag persistent homology, an
algebraic structure which encodes changes to homology groups of a simplicial
complex over a sequence of simplex additions and deletions. Provided that there
is an algorithm that multiplies two $n \times n$ matrices in $M(n)$ time, our
algorithm runs in $O(M(n) + n^2 \log^2 n)$ time for a sequence of $n$ additions
and deletions. In particular, the running time is $O(n^{2.376})$, by result of
Coppersmith and Winograd. The fastest previously known algorithm for this
problem
takes $O(n^3)$ time in the worst case.