Salman Parsa

Welcome to my homepage!

The following is a list of my research projects, with published results, in reverse chronological order.

Deciding Contractibility Of Curves on Boundary of 3-Manifolds

with É. Colin de Verdière.

In this project, we presented an exponential time algorithm for deciding the contractibilty of a closed curve with self-intersections on the boundary of a 3-manifold. The main idea is to extract the computational content of the proof of the Loop Theorem.

Preliminary version of the result is published in:

É. Colin de Verdière, S. Parsa, “Deciding Contractibility of a Non-Simple Curve on the Boundary of a 3-Manifold”, Proceedings of the twenty-eighth annual ACM-SIAM Symposium On Discrete Algorithms. 2017, 2691-2704

In this project, we presented an exponential time algorithm for deciding the contractibilty of a closed curve with self-intersections on the boundary of a 3-manifold. The main idea is to extract the computational content of the proof of the Loop Theorem.

Preliminary version of the result is published in:

É. Colin de Verdière, S. Parsa, “Deciding Contractibility of a Non-Simple Curve on the Boundary of a 3-Manifold”, Proceedings of the twenty-eighth annual ACM-SIAM Symposium On Discrete Algorithms. 2017, 2691-2704

Bounding the Number of d-Simplices of Embeddable Complexes

In this research, the objects of study are simplicial complexes that are embeddable into Euclidean space. It is a well-known fact that if a graph (i.e. a 1-d simplicial complex) embeds into the plane, then it can have at most a linear number of edges, in terms of number of vertices. The first higher dimensional analog would be the problem of upper bounding the number of triangles in 2-dimensional simplicial complexes that embed into the four dimensional Euclidean space. It is a conjecture by many, including B. Gruenbaum and G. Kalai that the correct asymptotic upper bound is the number vertices to the power of 2. In a more concice statement the conjecture is that the upper bound is 4 tiems the number of edges. This problem seems far from resolved.

In this work, I have given a critorion that the each intersection of link-complexes of three disjoint vertices of an embeddable complex must satisfy. This triple intersection is a subgraph of the 1-skeleton of given 2-complex. This graph has to be planar. In the paper I have also a weaker general statement for general dimension that is proved by means of elementary algebraic topology.

This result is published in:

S. Parsa, “On the Links of Vertices in Simplicial d-Complexes Embeddable in the Euclidean 2d-Space”, Discrete Comput Geom (2017). https://doi.org/10.1007/s00454-017-9936-1

In this work, I have given a critorion that the each intersection of link-complexes of three disjoint vertices of an embeddable complex must satisfy. This triple intersection is a subgraph of the 1-skeleton of given 2-complex. This graph has to be planar. In the paper I have also a weaker general statement for general dimension that is proved by means of elementary algebraic topology.

This result is published in:

S. Parsa, “On the Links of Vertices in Simplicial d-Complexes Embeddable in the Euclidean 2d-Space”, Discrete Comput Geom (2017). https://doi.org/10.1007/s00454-017-9936-1

Embedding Homotopy Types of 2-Complexes into 4-Space

In this research, I have shown by a new proof that each homotopy type of a 2-dimensional simplicial complex has a member simplicial complex that embeds into 4-space. In particular, any finitely presented group appears as a fundamental group of a 2-complex PL embeded into 4-space. These result had been known before, and I have independently proven them. These embeddings can be built in linear time, that implies, knowing that a 2-complex is embeddable in 4-space does not help with regard to efficiency of algorithmic problems related to its fundamental group.

The paper can be downloaded from here:

“Small Model 2-Complexes in 4-space and Applica?ons.” ArXiv e-prints, 1512.05152, 2015

The paper can be downloaded from here:

“Small Model 2-Complexes in 4-space and Applica?ons.” ArXiv e-prints, 1512.05152, 2015

The Computational Complexity of Betti Numbers: Reductions from

Matrix Rank

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.

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].

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].

An Efficient Algorithm for Raytracing

with A. Shishegar.

This is my first paper. It discusses a technique to accelerate the raytracing procedure where the environment is static.

“A Ray Tracing Acceleration Technique for Wave Propagation Modeling”, Proc. IEEE Asia–Pacific Microwave Conference , 2009.

This is my first paper. It discusses a technique to accelerate the raytracing procedure where the environment is static.

“A Ray Tracing Acceleration Technique for Wave Propagation Modeling”, Proc. IEEE Asia–Pacific Microwave Conference , 2009.