4 citations · 5 across the 4 of their papers we have counts for
6 papers · 1 filter
Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds
Nairen Cao, Shang-En Huang, Hsin-Hao Su
In this paper, we study parallel algorithms for the correlation clustering problem, where every pair of two different entities is labeled with similar or dissimilar. The goal is to…
Adaptive Massively Parallel Constant-round Tree Contraction
MohammadTaghi Hajiaghayi, Marina Knittel, Hamed Saleh +1
Miller and Reif's FOCS'85 classic and fundamental tree contraction algorithm is a broadly applicable technique for the parallel solution of a large number of tree problems. Additio…
Lower Bounds for Dynamic Distributed Task Allocation
Hsin-Hao Su, Nicole Wein
We study the problem of distributed task allocation in multi-agent systems. Suppose there is a collection of agents, a collection of tasks, and a demand vector, which specifies the…
Distributed Data Summarization in Well-Connected Networks
Hsin-Hao Su, Hoa T. Vu
We study distributed algorithms for some fundamental problems in data summarization. Given a communication graph of nodes each of which may hold a value initially, we focus…
Towards the Locality of Vizing's Theorem
Hsin-Hao Su, Hoa T. Vu
Vizing showed that it suffices to color the edges of a simple graph using colors, where is the maximum degree of the graph. However, up to this date, no efficient distri…
Optimal Gossip Algorithms for Exact and Approximate Quantile Computations
Bernhard Haeupler, Jeet Mohapatra, Hsin-Hao Su
This paper gives drastically faster gossip algorithms to compute exact and approximate quantiles. Gossip algorithms, which allow each node to contact a uniformly random other node…