BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

The Formula Complexity of Subgraph Isomorphism Rossman, Benjamin


I will report recent progress on the formula complexity of the (colorful) subgraph isomorphism problem. (1) In previous work with Li and Razborov (FOCS 2014), we showed that the AC0-circuit complexity of G-subgraph isomorphism is n^{Theta~(treewidth(G))}. In new work, I show that the AC0-formula complexity of G-subgraph isomorphism is n^{poly(treedepth(G))} via a generalization of the "pathset technique" of R. (STOC 2014). This result has connections to finite model theory (a new proof of an improved homomorphism preservation theorem) and graph minor theory (a new excluded-minor approximation of bounded treedepth, joint with Ken-ichi Kawarabayashi). (2) Another extension of the “pathset technique” gives optimal size-depth trade-offs, including a tight n^{Omega(dk^{1/d})} formula-size lower bound for distance-k st-connectivity for small d and k, improving recent results of Chen et al (STOC 2016).

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International