A Modification of the Sarkar-Wang Algorithm and an Analysis of its Computational Complexity

Hales, Jonathan; Karabash, Dmytro; Lock, Michael T.

A Modification of the Sarkar-Wang Algorithm and an Analysis of its Computational Complexity

Authors

Hales, Jonathan

Karabash, Dmytro

Lock, Michael T.

Description

The Sarkar-Wang algorithm computes the hat version of the Heegaard Floer homology of a closed oriented three manifold. This paper analyzes the computational complexity of the Sarkar-Wang algorithm; then the algorithm is modified to obtain a better bound. Then the computational complexity of calculating HFK hat from a Heegaard diagram by means of the modified Sarkar-Wang algorithm is also analyzed. Under certain assumptions it is shown that the modified Sarkar-Wang algorithm is faster than the Manolescu-Ozsvath-Sarkar algorithm.
14 pages, 4 figures, fixed two typos