Open Collections

The Formula Complexity of Subgraph Isomorphism

Banff International Research Station for Mathematical Innovation and Discovery

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).

Mathematics; Computer science; Theoretical computer science

video/mp4

Author affiliation: University of Toronto

2017-03-06

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/60803

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/