AMS Seminar w/ Kevin Pratt (Carnegie Mellon University) on Zoom

Title: Subgraph isomorphism via partial differentiation
Abstract: In this talk I will discuss a recent approach to the algorithmic problem of subgraph isomorphism: given a host graph G and target graph H, decide whether G contains a subgraph isomorphic to H. For simplicity, I will illustrate the approach in the case when H is a path. I will describe an algorithm whose runtime comes close to that of the state of the art, while using a new approach based on identifying polynomials with prescribed combinatorial supports (i.e., monomials appearing with nonzero coefficient), and whose partial derivatives (of all orders) span a vector space of small dimension. Connections to previous approaches and avenues for further improvement will also be discussed.
Part of this talk is based on joint work with Cornelius Brand.
 
Here is the link and the meeting info:
https://wse.zoom.us/j/98200438645?pwd=d3M3WEljc0sxd3BRQldUU3dudzhvdz09
Meeting ID: 982 0043 8645
Passcode: 374212