Salman Parsa
Postdoctoral Researcher
Ritter Hall
Deopartment of Computer Science
Saint Louis University, Saint Louis, MO. USA.

Welcome to my personal homepage!
Hardness of Segment Cover, Contiguous SAT and Visibility with Uncertain Obstacles
with Sh. Alipour

Consider SAT with the following restrictions. An input formula is in CNF form, and, there exists an ordering of the clauses in which clauses containing any fixed literal appear contiguously. We call this restricted SAT CONTIGUOUS SAT.  We also define the related problem SEGMENT COVER. In SEGMENT COVER, we are given a set of uncertain segments, each uncertain segment defined to be a random interval, chosen from two possible sub-intervals of the unit interval. Then, SEGMENT COVER asks if the probability of covering the entire unit interval is non-zero. We prove that SEGMENT COVER and hence CONTIGUOUS SAT are NP-hard. We further show that we can assume all intervals of SEGMENT COVER to be of equal lengths, this proves another problem called BCU to be NP-hard in dimension 1. Moreover, we also deduce hardness of approximation for CONTIGUOUS SAT and show it cannot have a PTAS, unless P= NP.
COCOA 2020
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.