CS Colloquium - Matching and Clustering via Higher-Order Symmetry Breaking

Oct 13, 2023

03:30 PM - 04:30 PM

MacLean Hall, 118

2 West Washington Street, Iowa City, IA 52240

Save to My Events

Hsin-Hao Su portrait - submitted


Hsin-Hao Su


Traditional studies on symmetry breaking focus on breaking symmetries on atomic objects such as nodes or edges (e.g., the maximal independent set problem and the maximal matching problem). Their generalizations to higher-order objects have the potential to be used for solving optimization problems in distributed and parallel models. In this talk, I will discuss how such primitives play a role in our two recent results as follows:

  1. A poly(1/ε, log n)-time (1-ε)-approximation algorithm for the maximum weight matching problem in the CONGEST and parallel models, with the latter using O(m) processors. The algorithm can also be adapted to the semi-streaming setting with poly(1/ε) passes.
  2. A poly(log n)-depth, Õ(m^{1.5})-work, (2.4+ε)-approximation parallel algorithm for disagreement-minimization correlation clustering, where m denotes the number of positively-correlated edges.


Hsin-Hao Su is an assistant professor in the computer science department at Boston College. His research interests lie in algorithms for combinatorial optimization problems in large-scale network settings, including distributed, parallel, and streaming settings. He obtained his PhD from the University of Michigan under the supervision of Seth Pettie in 2015. His thesis, titled "Algorithms for Fundamental Problems in Computer Networks," received the ACM-EATCS Principles of Distributed Computing Doctoral Dissertation Award. He did his postdoc at MIT with Nancy Lynch from 2015 to 2017.

Individuals with disabilities are encouraged to attend all University of Iowa–sponsored events. If you are a person with a disability who requires a reasonable accommodation in order to participate in this program, please contact in advance at