I received my PhD in Algorithms, Combinatorics, and Optimization from Georgia Institute of Technology, fortunate to be advised by Prasad Tetali. I am currently a visiting researcher at Carnegie Mellon University. My research has been supported by Transdisciplinary Research Institute for Advancing Data Science, Simons Institute for the Theory of Computing, Algorithms & Randomness Center, and the ACO program at Georgia Tech.
I am broadly interested in theoretical aspects of computer science, machine learning, and optimization. I have worked on:
I received my MSc in Machine Learning  Computer Science from Georgia Tech, College of Computing, and two BSc degrees from Computer Engineering and Electrical Engineering departments at Sharif University of Technology, majored in software engineering and communication systems.
On the BurerMonteiro Optimization for Rank Constrained Semidefinite Programming. 

Optimal Dispatch of Firefighters from Multiple Stations. 

Hardness and Approximation of Submodular Minimum Linear Ordering Problems. With Swati Gupta, Shengding Sun, Prasad Tetali, Michael C. Wigal. arXiv 45min summary The minimum linear ordering problem (MLOP) seeks to minimize an aggregated cost f(\cdot) due to an ordering \sigma of the items (say [n]), i.e., \min_{\sigma} \sum_{i\in [n]} f(E_{i,\sigma}), where E_{i,\sigma} is the set of items that are mapped by \sigma to indices at most i. This problem has been studied in the literature for various special cases of the cost function f, and in a general setting for a submodular or supermodular cost f [ITT2012]. Though MLOP was known to be NPhard for general submodular functions, it was unknown whether the special case of graphic matroid MLOP (with f being the matroid rank function of a graph) was polynomialtime solvable. Following this motivation, we explore related classes of linear ordering problems, including symmetric submodular MLOP, minimum latency vertex cover, and minimum sum vertex cover. We show that the most special cases of our problem, graphic matroid MLOP and minimum latency vertex cover, are both NPhard. We further expand the toolkit for approximating MLOP variants: using the theory of principal partitions, we show a 2\frac{1+\ell_{f}}{1+E} approximation to monotone submodular MLOP, where \ell_{f}=\frac{f(E)}{\max_{x\in E}f(\{x\})} satisfies 1 \leq \ell_f \leq E. Thus our result improves upon the best known bound of 2\frac{2}{1+E} by Iwata, Tetali, and Tripathi [ITT2012]. This leads to a 2\frac{1+r(E)}{1+E} approximation for the matroid MLOP, corresponding to the case when r is the rank function of a given matroid. Finally, we show that MLVC can be 4/3 approximated, matching the integrality gap of its vanilla LP relaxation. 

λ_{∞} & Maximum Variance Embedding: Measuring and Optimizing Connectivity of A Graph Metric. With Anand Louis, Mohit Singh, and Prasad Tetali. arXiv 

J2

Bridging Classical and Quantum with SDP initialized warmstarts for QAOA. To appear in ACM Transactions on Quantum Computing. With Reuben Tate, Creston Herold, Greg Mohler, and Swati Gupta. arXiv summary We study the Quantum Approximate Optimization Algorithm (QAOA) in the context of the MaxCut problem. Nearterm (noisy) quantum devices are only able to (accurately) execute QAOA at low circuit depths while QAOA requires a relatively high circuitdepth in order to "see" the whole graph. We introduce a classical preprocessing step that initializes QAOA with a biased superposition of all possible cuts in the graph, referred to as a warmstart. In particular, our initialization informs QAOA by a solution to a lowrank semidefinite programming relaxation of the MaxCut problem. Our experimental results show that this variant of QAOA, called QAOAWarm, is able to outperform standard QAOA on lower circuit depths with less training time (in the optimization stage for QAOA's variational parameters). We provide experimental evidence as well as theoretical intuition on performance of the proposed framework. 

C6

The Traveling Firefighter Problem. In ACDA 2021  Proceedings of SIAM Conference on Applied and Computational Discrete Algorithms, July 2021. With Alejandro Toriello, and Prasad Tetali. arXiv slides summary We studied variants of the Traveling Salesman Problem whose objective can be more efficient, fair, and adjustable to various applications, e.g., ridesharing from costumer vs server perspective, containment of wildfires, etc. In contrast to pathTSP, we generalize the objective to be an arbitrary norm of the delay/servicetime vector. We developed efficient randomized algorithms with approximate optimality guarantees for such APXhard problems in general metrics. We also provided an approximation preserving reduction from the problem with any Minkowski norm of the delay vector as the (nonlinear) objective, to a variant of TSP with a constant number of deadlines. 

C5

Improved Approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover. In SODA 2021  Proceedings of ACMSIAM Symposium on Discrete Algorithms, January 2021. With Nikhil Bansal, Jatin Batra, and Prasad Tetali. arXiv summary In min sum vertex cover (MSVC) the goal is to find an ordering of the vertices of a graph to minimize the average cover time of its edges. An edge is covered when one of its endpoints appears in the ordering. We give a 16/9 = 1.778 approximation for MSVC, and show a matching integrality gap for the natural LP relaxation. This improves upon the previous best 1.999946 approximation of Barenholz, Feige and Peleg. We also study a much more general problem known as multiple intents ranking, or generalized min sum set cover (GMSSC), wherein given a hypergraph, each hyperedge is considered covered by the first time when a given number of its vertices appear in the ordering. We give a 4.642 approximation algorithm for GMSSC, coming close to the best possible bound of 4, already for the classical special case of min sum set cover (MSSC) studied by Feige, Lovász and Tetali, and improving upon the previous best known bound of 12.4 due to Im, Sviridenko and van der Zwaan. Our algorithm is based on transforming the LP solution by a suitable kernel and applying randomized rounding. This also gives an LPbased 4 approximation for MSSC. As part of the analysis of our algorithm, we also derive an inequality on the lower tail of a sum of independent Bernoulli random variables, which might be of independent interest and broader utility. 

C4

Low Complexity Heart Rate Measurement from Wearable WristType Photoplethysmographic Sensors Robust to Motion Artifacts. In ICASSP 2018  Proceedings of 43^{rd} IEEE International Conference on Acoustics, Speech and Signal Processing, April 2018. With Mahdi B Mashhadi, Mahmoud Essalat, and Farokh Marvasti. pdf summary We presented a low complexity while accurate Heart Rate (HR) estimation technique from signals captured by Photoplethysmographic (PPG) sensors worn on the wrist during intensive physical exercise. Wristtype PPG signals experience severe Motion Artifacts (MA) that hinder efficient HR estimation especially during intensive physical exercises. To suppress the motion artifacts efficiently, simultaneous 3 dimensional acceleration signals are used as reference MAs. We introduced heuristics to recover, denoise, and postprocess the spectrum of the heart beat signal, to track and predict HR time series. The proposed method achieved an Average Absolute Error (AAE) of 1.19 Beats Per Minute (BPM) on the 12 benchmark PPG recordings in which subjects run at speeds of up to 15 km/h. This method also achieves an AAE of 2.17 BPM on the whole benchmark database of 23 recordings that include both running and arm movement activities. The proposed method achieved comparable accuracy with stateoftheart algorithms while at a significantly reduced computational cost which makes its standalone implementation on wearable devices feasible. The proposed algorithm achieves an average processing time of 32 milliseconds per input frames of length 8 seconds (2 channel PPG and 3D ACC signals) on a 3.2 GHz processor. 

C3

Routing in WellSeparated Pair Decomposition Spanners. In ICCG 2018  Proceedings of 1^{st} Iranian Conference on Computational Geometry, February 2018. With Fatemeh Baharifard, and Hamid ZarrabiZadeh. pdf summary We presented a local and arbitrary precise routing scheme for the wellseparated pair decomposition (WSPD) spanners, using compressed quadtrees. Given a point set P in the plane, a WSPD spanner is a geometric graph whose vertex set is P, and for each pair (A, B) in the WSPD of P, an edge is added to the graph from an arbitrary point in A to an arbitrary point in B. 

J1

Expand the Shares Together: EnvyFree Mechanisms with a Small Number of Cuts. In Algorithmica. With Masoud Seddighin, Mohammad Ghodsi, Reza Alijani, and Ahmad S Tajik. pdf summary We study the problem of fair division of a heterogeneous resource among strategic players. Given a divisible heterogeneous cake, we wish to divide the cake among n players in a way that meets the following criteria: (I) every player(weakly) prefers his allocated cake to any other player’s share (such notion is known as envyfreeness), (II) the mechanism is strategyproof (truthful), and (III) the number of cuts made on the cake is minimal. We provide methods, namely expansion process and expansion process with unlocking, for dividing the cake under different assumptions on the valuation functions of the players. 

C2

Envyfree mechanisms with minimum number of cuts. In AAAI 2017  Proceedings of 31^{st} AAAI Conference on Artificial Intelligence, February 2017. With Reza Alijani, Mohammad Ghodsi, Masoud Seddighin, and Ahmad S Tajik. pdf summary We study the problem of fair division of a heterogeneous resource among strategic players. Given a divisible heterogeneous cake, we wish to divide the cake among n players in a way that meets the following criteria: (I) every player(weakly) prefers his allocated cake to any other player’s share (such notion is known as envyfreeness), (II) the mechanism is strategyproof (truthful), and (III) the number of cuts made on the cake is minimal. We provide methods, namely expansion process and expansion process with unlocking, for dividing the cake under different assumptions on the valuation functions of the players. 

C1

Diversity Maximization via Composable Coresets. In CCCG 2015  Proceedings of 27^{th} Canadian Conference on Computational Geometry, August 2015. With Sepideh Aghamolaei, and Hamid ZarrabiZadeh. pdf summary Given a set S of points in a metric space, and a diversity measure div (.) defined over subsets of S, the goal of the diversity maximization problem is to find a subset T of size k that maximizes div(T). Motivated by applications in massive data processing, we consider the composable coreset framework in which a coreset for a diversity measure is called composable, if for any collection of sets and their corresponding coresets, the maximum diversity of the union of the coresets approximates the maximum diversity of the union of the sets. We present composable coresets with nearoptimal approximation factors for several notions of diversity, including remoteclique, remotecycle, and remotetree. We also prove a general lower bound on the approximation factor of composable coresets for a large class of diversity maximization problems. 

F2019 
Graduate Algorithms (CS6515)


S2019 
Graduate Algorithms (CS6515)


F2018 
Computability & Algorithms (CS6505)


F2016 
Design & Analysis of Algorithms (CE354)


S2016 
Artificial Intelligence (CE417), Data Structures & Algorithms (CE254)


S2015 
Advanced Programming (EE777), Data Structures & Algorithms (CE254)


F2014 
Artificial Intelligence (CE417)


On Rank Constrained Semideifinite Programming, CS Theory, CMU, Mar 2022
On Submodular Linear Ordering Problems, ACO, CMU, Oct 2021
Multiple Intents Scheduling, Two Sigma, Jul 2021
Warm Starts for Quantum Approximate Optimization Algorithm, INFORMS, Nov 2020
Minimum Sum Vertex Cover, Simons Institute for Theory of Computing, UC Berkeley, Oct 2020
NonConvex Optimization Landscape of a Kernel PCA, Georgia Tech, Oct 2020
Generalized Min Sum Set Cover, ACO, Georgia Tech, Sep 2020
On Maximum Variance Embedding, Hot CSE Seminar, Georgia Tech, Dec 2019.
Judge & Problem Design: IEEE International Programming Competition  IEEEXtreme 2020
Journal Review: IEEE Journal of Biomedical and Health Informatics 2018
Conference Review: Symposium on Computational Geometry 2016
Ranked 1^{st}  9^{th} IEEEXtreme International Programming Competition (2015, 2017)
Ranked 1^{st}  20^{th} National Scientific Olympiad in Computing. (2015)
Gold Medal  21^{st} National Olympiad in Informatics. (2012)