Colloquium - Are All Practical Planar Optimization Problems Easy?

April 1, 2020 - 4:00pm to 5:00pm
Zoom - See emails for details
Hsien-Chih Chang
Duke University

When analyzing data sets from real-world applications, many classical "efficient" algorithms that run in time quadratic to the input size are considered too slow to be practical.   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 on the input, whether they are points on surfaces, trajectories in the plane, or planar graphs.  Many such problems admit subquadratic or even near-linear time algorithms by exploiting various properties and tools that exist only in the plane.  Is it fair to claim that all planar optimization problems can be solved efficiently in practice?

In this talk, I will introduce a few topological and geometric tools that help us to design extremely efficient algorithms for some planar problems, including a characterization of planar metrics and succinct representations of planar graphs.  I will also demonstrate how topology reveals hidden structures in a problem, which allows us to abandon certain overly-optimistic attempts to solve planar optimization problems efficiently in a unified fashion.  We end the talk with some open problems for future research.

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.