46 citations · 101 across the 26 of their papers we have counts for
34 papers
Barely Monotone (min,+)-Convolution in Truly Subquadratic Time
MohammadTaghi Hajiaghayi, Danny Mittal, Saeed Seddighin
The (min,+)-convolution of two sequences A and B of length n is the sequence C with C[k] = min_{i+j=k} (A[i]+B[j]). For bounded inputs, whose entries are integers in {0,...,O(n)},…
Optimal Networks for Agentic Information Aggregation
MohammadHossein Bateni, Zahra Hadizadeh, MohammadTaghi Hajiaghayi +2
We study information aggregation in the networked learning model introduced by Kearns, Roth, and Ryu (SODA 2026). There is a fixed distribution over features and a common label…
Efficient Dynamic Algorithms for Graph Neural Networks with Non-Linear Propagation
Kiarash Banihashem, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz +2
Graph Neural Networks (GNNs) are widely used for representation learning on graphs, but most methods assume static topologies, making them inefficient on evolving networks where ed…
Optimal Rates for Agentic Networked Information Aggregation
MohammadHossein Bateni, Zahra Hadizadeh, MohammadTaghi Hajiaghayi +2
Building on the pioneering paper of Kearns, Roth, and Ryu (SODA'26), we study information aggregation in a networked learning model. The model captures a central pattern in agentic…
Optimal Contest Beyond Convexity
Negin Golrezaei, MohammadTaghi Hajiaghayi, Suho Shin
In the contest design problem, there are strategic contestants, each of whom decides an effort level. A contest designer with a fixed budget must then design a mechanism that a…
Single-Sample Bilateral Trade with a Broker
MohammadTaghi Hajiaghayi, Gary Peng, Suho Shin
We initiate the study of single-sample bilateral trade with a broker, drawing an analogy to the setting of single-sample bilateral trade without a broker considered in Babaioff et…
Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond
Kiarash Banihashem, Jeff Giliberti, Samira Goudarzi +3
In this paper, we study the fundamental problems of maintaining the diameter and a -center clustering of a dynamic point set , where points may be insert…
How Bad Is Forming Your Own Multidimensional Opinion?
Kiarash Banihashem, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz +2
Understanding the formation of opinions on interconnected topics within social networks is of significant importance. It offers insights into collective behavior and decision-makin…
The Expiration Streaming Model: Diameter, -Center, Counting, Sampling, and Friends
Lotte Blank, Sergio Cabello, MohammadTaghi Hajiaghayi +5
An important thread in the study of data-stream algorithms focuses on settings where stream items are active only for a limited time. We introduce a new expiration model, where eac…
Pandora with Inaccurate Priors
Kiarash Banihashem, Xiang Chen, MohammadTaghi Hajiaghayi +4
We investigate the role of inaccurate priors for the classical Pandora's box problem. In the classical Pandora's box problem we are given a set of boxes each with a known cost and…
Gains-from-Trade in Bilateral Trade with a Broker
Ilya Hajiaghayi, MohammadTaghi Hajiaghayi, Gary Peng +1
We study bilateral trade with a broker, where a buyer and seller interact exclusively through the broker. The broker strategically maximizes her payoff through arbitrage by trading…
A Dynamic Algorithm for Weighted Submodular Cover Problem
Kiarash Banihashem, Samira Goudarzi, MohammadTaghi Hajiaghayi +2
We initiate the study of the submodular cover problem in dynamic setting where the elements of the ground set are inserted and deleted. In the classical submodular cover problem, w…
Prize-Collecting Steiner Tree: A 1.79 Approximation
Ali Ahmadi, Iman Gholami, MohammadTaghi Hajiaghayi +2
Prize-Collecting Steiner Tree (PCST) is a generalization of the Steiner Tree problem, a fundamental problem in computer science. In the classic Steiner Tree problem, we aim to conn…
Replication-proof Bandit Mechanism Design with Bayesian Agents
Suho Shin, Seyed A. Esmaeili, MohammadTaghi Hajiaghayi
We study the problem of designing replication-proof bandit mechanisms when agents strategically register or replicate their own arms to maximize their payoff. Specifically, we cons…
Fair Polylog-Approximate Low-Cost Hierarchical Clustering
Marina Knittel, Max Springer, John Dickerson +1
Research in fair machine learning, and particularly clustering, has been crucial in recent years given the many ethical controversies that modern intelligent systems have posed. Ah…
Dynamic Non-monotone Submodular Maximization
Kiarash Banihashem, Leyla Biabani, Samira Goudarzi +3
Maximizing submodular functions has been increasingly used in many applications of machine learning, such as data summarization, recommendation systems, and feature selection. More…
Online Advertisements with LLMs: Opportunities and Challenges
Soheil Feizi, MohammadTaghi Hajiaghayi, Keivan Rezaei +1
This paper explores the potential for leveraging Large Language Models (LLM) in the realm of online advertising systems. We introduce a general framework for LLM advertisement, con…
2-Approximation for Prize-Collecting Steiner Forest
Ali Ahmadi, Iman Gholami, MohammadTaghi Hajiaghayi +2
Approximation algorithms for the prize-collecting Steiner forest problem (PCSF) have been a subject of research for over three decades, starting with the seminal works of Agrawal,…
Stochastic Matching with Few Queries: Approximation
Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi
Suppose that we are given an arbitrary graph and know that each edge in is going to be realized independently with some probability . The goal in the stochastic m…
String Matching with Wildcards in the Massively Parallel Computation Model
MohammadTaghi Hajiaghayi, Hamed Saleh, Saeed Seddighin +1
We study distributed algorithms for string matching problem in presence of wildcard characters. Given a string T (a text), we look for all occurrences of another string P (a patter…
Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time
Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi +2
We present the first algorithm for maintaining a maximal independent set (MIS) of a fully dynamic graph---which undergoes both edge insertions and deletions---in polylogarithmic ti…
Optimal Strategies of Blotto Games: Beyond Convexity
Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan +3
The Colonel Blotto game, first introduced by Borel in 1921, is a well-studied game theory classic. Two colonels each have a pool of troops that they divide simultaneously among a s…
Exponentially Faster Massively Parallel Maximal Matching
Soheil Behnezhad, MohammadTaghi Hajiaghayi, David G. Harris
The study of approximate matching in the Massively Parallel Computations (MPC) model has recently seen a burst of breakthroughs. Despite this progress, however, we still have a far…
Fair Allocation of Indivisible Goods: Improvement and Generalization
Mohammad Ghodsi, MohammadTaghi Hajiaghayi, Masoud Seddighin +2
We study the problem of fair allocation for indivisible goods. We use the the maxmin share paradigm introduced by Budish as a measure for fairness. Procaccia and Wang (EC'14) were…