Salman Parsa

Current Address:

Ritter Hall

Deopartment of Computer Science

Saint Louis University, Saint Louis, MO. USA.

email: salman.parsa@slu.edu

Ritter Hall

Deopartment of Computer Science

Saint Louis University, Saint Louis, MO. USA.

email: salman.parsa@slu.edu

Welcome to my personal homepage!

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

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.