Events Calendar

Speaker

Hsin-Hao Su

Abstract

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.

Bio

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.