Salman Parsa
Current Address:
Ritter Hall
Deopartment of Computer Science
Saint Louis University, Saint Louis, MO. USA.
email: salman.parsa@slu.edu

Welcome to my personal homepage!
The Computational Complexity of Betti Numbers:
Reductions  from  Matrix Rank

with H. Edelsbrunner. 
In this paper we have shown that computing the betti numbers of 2-dimensional simplicial complexes is essentially equivalent to computing the rank of sparse matrices. In general, we reduced computing the rank of a matrix to computing the second betti number of a 2-complex, which can be even embeddable into 4-space.  
 
H. Edelsbrunner, S. Parsa, “On the computational complexity of Betti numbers: reductions from matrix rank”, Proceedings of the twenty-fifth annual ACM-SIAM Symposium On Discrete Algorithms. 2014, 152-160.

Dynamic Reeb Graphs 
In my PhD thesis I have given a general framework for an algorithm to update a Reeb graph under a change in the order of the vertices of the complex. However, it turns out that this problem cannot have a polylogarithmic algorithm, due to the fact that one can (almost!) model a dynamic graph connectiity problem using it. You can access my PhD thesis from the link below. 
 

An Efficient Algorithm for the Reeb Graph 
In this work, I gave an O(m log m) algorithm for computing the Reeb graph. Here m is the total number of simplices in the given simplicial complex. The input can be of arbitrary dimension. 
 
S. Parsa, “A Deterministic O ( m log m ) Time Algorithm for the Reeb Graph” . Discrete & Computational Geometry 49(4): 864-878 (2013) [ First version in SOCG 2012]. 
 
Please contact me if you need the code for this project.