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