Experience

Quantitative Researcher

Jump Trading,
Jump Core Strategies

Since July 2022

Researcher

Carnegie Mellon University

Sep 2021 - May 2022

Quantitative Research Intern

Two Sigma Investments,
Machine Learning

May 2021 - Jul 2021

Researcher

University of California, Berkeley,
Simons Institute for the Theory of Computing

Fall 2020 & 2021

Graduate Research Assistant

Georgia Institute of Technology

Aug 2017 - May 2022

Research Assistant

The Chinese University of Hong Kong

Jul 2016 - Aug 2016

Publications

• J4

  Hardness and approximation of submodular minimum linear ordering problems

  M Farhadi, S Gupta, S Sun, P Tetali, M C Wigal
  

  Mathematical Programming 208 (1), 277-318, 2024

  Summary Talk Springer

  

  The Story: From search engines to large language models to logistics, many real-world systems involve making sequential decisions to accomplish tasks. These decisions can be modeled as optimization problems, where a penalty function evaluates prefixes of the ordering, aiming to optimize expected satisfaction or objective completion. We focus on a fundamental case where this penalty function is submodular, capturing diminishing returns and enabling efficient approximations for diverse applications like query optimization, task scheduling, and resource allocation.

  TL;DR: We provided refined approximation bounds for Minimum Linear Ordering Problems under monotonic matroid constraints, along with a new algorithm using principal partitions. We also proved submodular MLOP is NP-hard, particularly graph-matroid MLOP.

• J3

  On Min Sum Vertex Cover and Generalized Min Sum Set Cover

  N Bansal, J Batra, M Farhadi, P Tetali
  

  SIAM Journal on Computing 52 (2), 327-357, 2023

  Summary SIAM

  

  The Story: Vertex cover and set cover are cornerstone problems in computer science, underpinning applications in machine learning, information retrieval, operations research, and network design. A counterpart emerges when vertices or elements are selected sequentially, aiming to minimize the expected coverage time of edges or sets. This leads to problems like Min Sum Vertex Cover and Min Sum Set Cover. Despite an extensive literature, the approximability of such problems remains elusive.

  TL;DR: We provide new insights and algorithms that push the state of the art, particularly for Min Sum Vertex Cover and Generalized Min Sum Set Cover. Our analyses further led to introducing a new tail bound for sum of independent Bernoulli random variables.

• J2

  Bridging classical and quantum with SDP initialized warm-starts for QAOA

  R Tate, M Farhadi, C Herold, G Mohler, S Gupta
  

  ACM Transactions on Quantum Computing 4 (2), 1-39, 2023

  Summary ACM

  

  The Story: The Quantum Approximate Optimization Algorithm (QAOA) is a promising method for solving combinatorial optimization problems but struggles on noisy, near-term quantum devices limited to shallow circuits. We introduced a warm-start approach using semidefinite programming (SDP) relaxations to initialize QAOA with better starting points. This enhances its performance at shallow depths, enabling better solutions on current quantum hardware and improving its practical applicability.

  TL;DR: We provide theoretical guarantees and extensive experimental results, demonstrating the effectiveness of the proposed warm start QAOA in solving Max-Cut problems.

• A3

  Multi Purpose Routing: New Perspectives and Approximation Algorithms

  M Farhadi, J Moondra, P Tetali, A Toriello
  

  2023

  Summary

  

  The Story: In real-world applications, delays can incur costs that grow non-linearly, such as moving towards the optimal portfolio or delivering services to customers. We study a natural generalization of the fundamental Traveling Salesman Problem (TSP) where instead of the latest visit time, a Minkowski norm of the delays is minimized. This captures a wide range of applications, and introduces new theoretical and algorithmic challenges.

  TL;DR: We provide improved approximation algorithms for single vehicle and multi-vehicle Lp-TSP problems.

• C6

  The Traveling Firefighter Problem

  M Farhadi, A Toriello, P Tetali
  

  SIAM Conference on Applied and Computational Discrete Algorithms (ACDA21), 205-216, 2021

  Summary Slides SIAM

  

  The Story: Imagine scheduling a firefighter’s route to extinguish multiple wildfires, where the delay in reaching each fire increases damage not linearly but quadratically. We modeled this situation with the Traveling Firefighter Problem (TFP), and more generally the Lp-Traveling Salesman Problem, which generalizes delay costs to balance fairness and efficiency. Models like these are critical for solving real-world challenges in emergency response, supply chains, and ride-sharing, where diverse metrics of delay require adaptable, efficient solutions.

  TL;DR: We presented polynomial-time approximation schemes for structured metrics, such as Euclidean and tree networks, alongside a constant factor approximation for Traveling Firefighter Problem, and a factor 8 approximation for the all-norm scenario where the answer is approximately optimal with respect to the optimal answer for any norm. Moreover, we showed an approximate all-norm objective is impossible to guarantee within a factor of 1.78.

  Open PDF in a new tab

• C5

  Improved approximations for min sum vertex cover and generalized min sum set cover

  N Bansal, J Batra, M Farhadi, P Tetali
  

  Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), 998-1005, 2021

  Summary SIAM

  

  The Story: For a search engine, or recommendation system, results may cover different intents, and the sequence of presenting them impacts coverage of such intents. This challenge is formally known as multiple intents ranking or Generalized Min Sum Set Cover (GMSSC), extending classical problems like Min Sum Set Cover, where sets are covered by their first member in the sequence, and Min Sum Vertex Cover, a special case involving graphs.

  TL;DR: We introduce kernel alpha-point scheduling, a new method for rounding Linear Programming relaxations of such scheduling problems, that achieves improved approximation guarantees for GMSSC and Min Sum Vertex Cover after decades of stagnation.

• A2

  λ∞ & Maximum Variance Embedding: Measuring and Optimizing Connectivity of A Graph Metric

  M Farhadi, A Louis, M Singh, P Tetali
  

  2020

  Summary

  

  The Story: Measuring and optimizing graph connectivity is crucial for robust communication, data security, and system control. A counterpart to the dominant spectral gap of the graph, λ₂, is λ∞ that is another Poincaré-type parameter, offering a more nuanced perspective on the graph's vertex connectivity. On the optimization side, maximizing connectivity and convergence rate of Markov Chains on graphs translates to Maximum Variance Embedding, through convex duality; a non-linear dimension reduction problem that is also fundamental in machine learning and data analysis, also known as Maximum Variance Unfolding.

  TL;DR: We study complexity of computing λ∞ and Maximum Variance Embedding, and analyze approximation bounds in low dimensions.

• J1

  Expand the shares together: envy-free mechanisms with a small number of cuts

  M Seddighin, M Farhadi, M Ghodsi, R Alijani, A S Tajik
  

  Algorithmica 81, 1728-1755, 2019

  Summary Springer

  

  The Story: Imagine dividing a multi-layered cake among friends, where each layer represents different preferences (chocolate for some, vanilla for others). The challenge isn’t just fairness—ensuring everyone feels their share is at least as good as others'—but also honesty, where no one should gain by lying about their preferences, and efficiency, minimizing cuts to preserve the cake's integrity. Beyond desserts, this has real-world applications, like assigning tasks or advertisement slots, where fairness, trust, and efficiency are paramount.

  TL;DR: We developed heuristic mechanisms for fair division of a heterogeneous resource among strategic players, ensuring envy-freeness, truthfulness, and minimal cuts. Key contributions include the Expansion Process and its extension, Expansion with Unlocking, which achieve allocations with O(nm) cuts for piecewise constant valuations with m intervals per player. Empirical results demonstrate the methods' efficiency, producing near-optimal cuts close to the theoretical minimum.

• C4

  Low Complexity Heart Rate Measurement from Wearable Wrist-Type Photoplethysmographic Sensors Robust to Motion Artifacts

  M B Mashhadi, M Farhadi, M Essalat, F Marvasti
  

  IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 921-924, 2018

  Summary IEEE

  

  The Story: Wearable devices face challenges due to motion artifacts. This paper introduces an algorithm combining accelerometer data and advanced signal processing to efficiently filter noise and deliver reliable, real-time heart rate data, advancing the accuracy and usability of modern fitness and medical wearables.

  TL;DR: Incorporating Auto-regressive spectrum estimation, spectral division, and a cumulative spectrum (CUMSPEC) transformation, we robustly extract heartbeat signal from noisy PPG signals, making it feasible for real-time implementation on low-power processors in wearable devices. With an average processing time of 32 milliseconds per input frame, this approach achieves a realtime factor of %1 on conventional processors, bridging the gap between accuracy and computational efficiency, and is a benchmark for future research in wearable health monitoring.

• C3

  Routing in well-separated pair decomposition spanners

  F Baharifard, M Farhadi, H Zarrabi-Zadeh
  

  Iranian Conference on Computational Geometry, 25-28, 2018

  Summary PDF

  

  The Story: Efficient routing in large, distributed networks often struggles with balancing path efficiency and memory use. Well-separated pair decomposition spanners simplify this by representing network points as a graph with sparse connectivity yet near-optimal paths. However, routing, especially using local information remains a challenge.

  TL;DR: In this study we proposed new algorithms for near optimal routing for spanners constructed based on compressed quadtrees.

• C2

  Envy-free mechanisms with minimum number of cuts

  M Seddighin, R Alijani, A S Tajik, M Farhadi, M Ghodsi
  

  Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 312-318, 2017

  Summary AAAI

  

  The Story: Fairly dividing resources is crucial in applications like ad scheduling or computational resource allocation, where fragmented divisions can cause inefficiencies, such as increased overhead or reduced impact. In this study, we model each player's valuation as uniform over an interval, focusing on minimizing divisions while ensuring fairness and honesty, paving the way for more efficient resource allocation mechanisms.

  TL;DR: This study introduces the Expansion with Unlocking method, which ensures envy-free and truthful allocations. The approach achieves an average of fewer than 2 pieces per player. By leveraging structured expansions and resolving locked situations, it provides practical, near-optimal solutions for fair division with efficient number of cuts.

• A1

  Realtime heart rate monitoring using photoplethysmographic (PPG) signals during intensive physical exercises

  M B Mashhadi, M Essalat, F Marvasti, M Farhadi
  

  2016

  Summary bioRxiv

  

  The Story: Heart rate monitoring during exercise is vital yet challenging due to interference from body movements. This paper introduces new heuristics for denoising the spectrum of heartbeat and tracking the heartbeat time series, ensuring accurate and real-time outputs. The framework’s ability to operate efficiently on wearable devices made it practical for everyday use.

  TL;DR: We introduced new heuristics, including a transformation of the spectrum along with a lazy update mechanism, to accurately track heart rate, using minimal computational resources.

• C1

  Diversity Maximization via Composable Coresets

  S Aghamolaei, H Zarrabi-Zadeh, M Farhadi
  

  Canadian Conference on Computational Geometry (CCCG), 38-48, 2015

  Summary PDF

  

  The Story: In big data environments, processing massive datasets distributed across multiple systems demands efficient algorithms. The composable coreset framework addresses this by allowing each system to create a compact summary of its data, preserving key properties like diversity. These summaries, or coresets, are then sent to a central server, enabling scalable computation within the MapReduce paradigm. This approach is essential for tasks like selecting products to showcase variety, search results, or planning facilities to maximize coverage, where identifying the most diverse subset is critical yet computationally challenging.

  TL;DR: Our analyses achieve tighter approximation factors across several metrics. Noteably, for the remote-clique problem, we improved the previous approximation factor of 51 to 6 for disjoint sets and 12.6 in general case. Similar improvements were presented for the remote-tree, remote-cycle, remote-bipartition, and other metrics. We complemented these results with a lower bound of 3.

Talks

Awards