MohammadTaghi Hajiaghayi

research

∙ 06/01/2023

Dynamic Algorithms for Matroid Submodular Maximization

Submodular maximization under matroid and cardinality constraints are cl...

0 Kiarash Banihashem, et al. ∙

research

∙ 05/25/2023

Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements

We consider the problem of fair allocation of indivisible goods or chore...

0 MohammadTaghi Hajiaghayi, et al. ∙

research

∙ 05/24/2023

Dynamic Constrained Submodular Optimization with Polylogarithmic Update Time

Maximizing a monotone submodular function under cardinality constraint k...

0 Kiarash Banihashem, et al. ∙

research

∙ 05/18/2023

Fault-Tolerant Consensus in Quantum Networks

Fault-tolerant consensus is about reaching agreement on some of the inpu...

0 MohammadTaghi Hajiaghayi, et al. ∙

research

∙ 05/04/2023

Delegating to Multiple Agents

We consider a multi-agent delegation mechanism without money. In our mod...

0 MohammadTaghi Hajiaghayi, et al. ∙

research

∙ 03/08/2023

Optimal Sparse Recovery with Decision Stumps

Decision trees are widely used for their low computational cost, good pr...

0 Kiarash Banihashem, et al. ∙

research

∙ 02/15/2023

Bandit Social Learning: Exploration under Myopic Behavior

We study social learning dynamics where the agents collectively follow a...

0 Kiarash Banihashem, et al. ∙

research

∙ 02/08/2023

Weighted Edit Distance Computation: Strings, Trees and Dyck

Given two strings of length n over alphabet Σ, and an upper bound k on t...

0 Debarati Das, et al. ∙

research

∙ 10/13/2022

Online Algorithms for the Santa Claus Problem

The Santa Claus problem is a fundamental problem in fair division: the g...

0 MohammadTaghi Hajiaghayi, et al. ∙

research

∙ 09/15/2022

Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance

Computing the edit distance of two strings is one of the most basic prob...

0 Debarati Das, et al. ∙

research

∙ 05/29/2022

Generalized Stochastic Matching

In this paper, we generalize the recently studied Stochastic Matching pr...

0 Alireza Farhadi, et al. ∙

research

∙ 05/27/2022

Generalized Reductions: Making any Hierarchical Clustering Fair and Balanced with Low Cost

Clustering is a fundamental building block of modern statistical analysi...

10 Marina Knittel, et al. ∙

research

∙ 05/27/2022

Adaptive Massively Parallel Algorithms for Cut Problems

We study the Weighted Min Cut problem in the Adaptive Massively Parallel...

0 MohammadTaghi Hajiaghayi, et al. ∙

research

∙ 05/26/2022

Analysis of a Learning Based Algorithm for Budget Pacing

In this paper, we analyze a natural learning algorithm for uniform pacin...

0 MohammadTaghi Hajiaghayi, et al. ∙

research

∙ 03/24/2022

Improved Communication Complexity of Fault-Tolerant Consensus

Consensus is one of the most thoroughly studied problems in distributed ...

0 MohammadTaghi Hajiaghayi, et al. ∙

research

∙ 11/02/2021

Adaptive Massively Parallel Constant-round Tree Contraction

Miller and Reif's FOCS'85 classic and fundamental tree contraction algor...

0 MohammadTaghi Hajiaghayi, et al. ∙

research

∙ 06/01/2021

Differentially Private Densest Subgraph

Given a graph, the densest subgraph problem asks for a set of vertices s...

0 Alireza Farhadi, et al. ∙

research

∙ 01/13/2021

Improved Hierarchical Clustering on Massive Datasets with Broad Guarantees

Hierarchical clustering is a stronger extension of one of today's most i...

1 MohammadTaghi Hajiaghayi, et al. ∙

research

∙ 07/14/2020

Almost Envy-freeness, Envy-rank, and Nash Social Welfare Matchings

Envy-free up to one good (EF1) and envy-free up to any good (EFX) are tw...

0 Alireza Farhadi, et al. ∙

research

∙ 03/16/2020

Approximating LCS in Linear Time: Beating the √(n) Barrier

Longest common subsequence (LCS) is one of the most fundamental problems...

0 MohammadTaghi Hajiaghayi, et al. ∙

research

∙ 03/08/2020

Inverse Feature Learning: Feature learning based on Representation Learning of Error

This paper proposes inverse feature learning as a novel supervised featu...

0 Behzad Ghazanfari, et al. ∙

research

∙ 02/27/2020

Stochastic Matching with Few Queries: (1-ε) Approximation

Suppose that we are given an arbitrary graph G=(V, E) and know that each...

0 Soheil Behnezhad, et al. ∙

research

∙ 02/26/2020

Asymmetric Streaming Algorithms for Edit Distance and LCS

The edit distance (ED) and longest common subsequence (LCS) are two fund...

0 Alireza Farhadi, et al. ∙

research

∙ 02/26/2020

Streaming with Oracle: New Streaming Algorithms for Edit Distance and LCS

The edit distance (ED) and longest common subsequence (LCS) are two fund...

0 Alireza Farhadi, et al. ∙

research

∙ 12/22/2019

Approximate Maximum Matching in Random Streams

In this paper, we study the problem of finding a maximum matching in the...

0 Alireza Farhadi, et al. ∙

research

∙ 11/29/2019

Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)

(see paper for full abstract) Given a vertex-weighted directed graph G...

0 Rajesh Chitnis, et al. ∙

research

∙ 10/25/2019

Massively Parallel Algorithms for String Matching with Wildcards

We study distributed algorithms for string matching problem in presence ...

0 MohammadTaghi Hajiaghayi, et al. ∙

research

∙ 10/09/2019

Prophets, Secretaries, and Maximizing the Probability of Choosing the Best

Suppose a customer is faced with a sequence of fluctuating prices, such ...

0 Hossein Esfandiari, et al. ∙

research

∙ 09/08/2019

Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time

We present the first algorithm for maintaining a maximal independent set...

0 Soheil Behnezhad, et al. ∙

research

∙ 09/07/2019

Computing Stackelberg Equilibria of Large General-Sum Games

We study the computational complexity of finding Stackelberg Equilibria ...

0 Avrim Blum, et al. ∙

research

∙ 05/20/2019

Subcubic Equivalences Between Graph Centrality Measures and Complementary Problems

Despite persistent efforts, there is no known technique for obtaining un...

0 Mahdi Boroujeni, et al. ∙

research

∙ 05/05/2019

MapReduce Meets Fine-Grained Complexity: MapReduce Algorithms for APSP, Matrix Multiplication, 3-SUM, and Beyond

Distributed processing frameworks, such as MapReduce, Hadoop, and Spark ...

0 MohammadTaghi Hajiaghayi, et al. ∙

research

∙ 01/30/2019

Online Pandora's Boxes and Bandits

We consider online variations of the Pandora's box problem (Weitzman. 19...

0 Hossein Esfandiari, et al. ∙

research

∙ 01/14/2019

Optimal Strategies of Blotto Games: Beyond Convexity

The Colonel Blotto game, first introduced by Borel in 1921, is a well-st...

0 Soheil Behnezhad, et al. ∙

research

∙ 01/11/2019

Exponentially Faster Massively Parallel Maximal Matching

The study of graph problems in the Massively Parallel Computations (MPC)...

0 Soheil Behnezhad, et al. ∙

research

∙ 11/30/2018

Fast Algorithms for Knapsack via Convolution and Prediction

The knapsack problem is a fundamental problem in combinatorial optimizat...

0 MohammadHossein Bateni, et al. ∙

research

∙ 11/09/2018

Polynomial-time Approximation Scheme for Minimum k-cut in Planar and Minor-free Graphs

The k-cut problem asks, given a connected graph G and a positive integer...

0 MohammadHossein Bateni, et al. ∙

research

∙ 11/08/2018

Stochastic Matching with Few Queries: New Algorithms and Tools

We consider the following stochastic matching problem on both weighted a...

0 Soheil Behnezhad, et al. ∙

research

∙ 11/04/2018

Lower Bounds for External Memory Integer Sorting via Network Coding

Sorting extremely large datasets is a frequently occuring task in practi...

0 Alireza Farhadi, et al. ∙

research

∙ 09/11/2018

Massively Parallel Dynamic Programming on Trees

Dynamic programming is a powerful technique that is, unfortunately, ofte...

0 MohammadHossein Bateni, et al. ∙

research

∙ 07/17/2018

Massively Parallel Symmetry Breaking on Sparse Graphs: MIS and Maximal Matching

The success of massively parallel computation (MPC) paradigms such as Ma...

0 Soheil Behnezhad, et al. ∙

research

∙ 04/11/2018

Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce

The edit distance between two strings is defined as the smallest number ...

0 Mahdi Boroujeni, et al. ∙

research

∙ 02/28/2018

Brief Announcement: Semi-MapReduce Meets Congested Clique

Graph problems are troublesome when it comes to MapReduce. Typically, to...

0 Soheil Behnezhad, et al. ∙

research

∙ 10/30/2017

Prophet Secretary for Combinatorial Auctions and Matroids

The secretary and the prophet inequality problems are central to the fie...

0 Soheil Ehsani, et al. ∙

research

∙ 09/30/2017

On the Complexity of Chore Division

We study the proportional chore division problem where a protocol wants ...

0 Alireza Farhadi, et al. ∙

research

∙ 04/30/2012

A Game-Theoretic Model Motivated by the DARPA Network Challenge

In this paper we propose a game-theoretic model to analyze events simila...

0 Rajesh Chitnis, et al. ∙

research

∙ 05/03/2011

Parameterized Complexity of Problems in Coalitional Resource Games

Coalition formation is a key topic in multi-agent systems. Coalitions en...

0 Rajesh Chitnis, et al. ∙

MohammadTaghi Hajiaghayi

Featured Co-authors