Abstract: In the modern era of data analysis, many classical "efficient" algorithms that run in time quadratic to the input size are considered too slow in practice.   Fine-grained complexity has been established recently in response to the need for a theory with better predictive power.  However, only few problems have been proven to be hard under the new theory if we assume extra geometric or topological structure, say when the input is planar.  This is natural due to the fact that many such problems admit extremely fast algorithms by exploiting various tools and properties that exist only in the plane.  What can we say about the difficulty of planar optimization problems?  Is it fair to claim that most problems in the plane can be solved efficiently in practice? In this talk, I will introduce a few topological tools that help us to design extremely efficient algorithms in the plane (and more generally, on meshes and surfaces), including a characterization of planar metrics and succinct representations of planar graphs.  More surprisingly, I will demonstrate how topology also reveals hidden structures in problems that are seemly unrelated at first, which allows us to prove new conditional lower bounds for other planar optimization problems.  We end the talk with some open problems for future research.

Bio: Hsien-Chih Chang is a postdoctoral researcher in theoretical computer science at Duke University.  He obtained his Ph.D. from University of Illinois at Urbana-Champaign in 2018 under the supervision of Prof. Jeff Erickson.  His main research interests include discrete and computational topology and geometry, graph theory and algorithms, and applications to the rest of computer science.  His current work focuses on applying topological tools to understand the efficiency of computation.