Please note: This seminar will take place in DC 1304 and online.
Shyan Akmal, Klaus Tschira Boost fellow and Postdoctoral researcher
Max Planck Institute for Informatics
One of the most basic questions about finding patterns in data is the Induced Subgraph Detection problem. In this problem, we are given a small pattern graph and a large host graph, and are tasked with determining if the host contains the pattern as an induced subgraph. A dream goal of fine-grained complexity is to fully classify those patterns for which Induced Subgraph Detection is easy to solve, and those for which it becomes difficult. In this talk, we present some recent, surprising progress on this classification question, centered around a particularly suspicious pattern known as the 4-cycle.
Bio: Shyan Akmal is a Klaus Tschira Boost fellow and postdoctoral researcher at the Max Planck Institute for Informatics, working on problems in graph algorithms and algebraic methods in computer science. Previously, he was a Siebel scholar at MIT, where he completed his PhD under the supervision of Virginia Vassilevska Williams and Ryan Williams.
To attend this seminar in person, please go to DC 1304. You can also attend virtually on Zoom.