Fall 2016

Lower Bounds for Subgraph Isomorphism and Consequences in First-Order Logic

Tuesday, November 8th, 2016 9:30 am10:30 am

Add to Calendar

In this talk, I will survey results in circuit complexity that relate the AC0 circuit & formula size of the colored G-subgraph isomorphism problem to the tree-width & tree-depth of the graph G. These lower bound have consequences in first-order logic: (1) showing that the number-of-variables hierarchy is strict on ordered graphs, and (2) a new proof that the Homomorphism Preservation Theorem of classical model theory remains valid when restricted to finite structures.