31 citations · 61 across the 13 of their papers we have counts for
18 papers
How Hard Is It for Message-Passing GNNs to Simulate One Weisfeiler-Lehman Color-Refinement Step?
Guanyu Cui, Yuhe Guo, Zhewei Wei +1
Message-passing graph neural networks (MPGNNs) are commonly compared with the Weisfeiler-Lehman (WL) color-refinement procedure, but this comparison does not quantify the resource…
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…
Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights
Vikrant Ashvinkumar, Aaron Bernstein, Nairen Cao +5
This paper presents parallel, distributed and quantum algorithms for single-source shortest paths when edges can have negative weights (negative-weight SSSP). We show a framework t…
-Approximate Maximum Weighted Matching in Distributed, Parallel, and Semi-Streaming Settings
Shang-En Huang, Hsin-Hao Su
The maximum weighted matching (MWM) problem is one of the most well-studied combinatorial optimization problems in distributed graph algorithms. Despite a long development on the p…
Narrowing the LOCAL$\unicode{x2013}$CONGEST Gaps in Sparse Networks via Expander Decompositions
Yi-Jun Chang, Hsin-Hao Su
Many combinatorial optimization problems can be approximated within factors in rounds in the LOCAL model via network decompositions [Ghaffari…
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…