An improved homomorphism preservation theorem from lower bounds in circuit complexity
Previous work of the author  showed that the Homomorphism Preservation Theorem of classical model theory remains valid when its statement is restricted to finite structures. In this paper, we give a new proof of this result via a reduction to lower bounds in circuit complexity, specifically on the AC0 formula size of the colored subgraph isomorphism problem. Formally, we show the following: if a first-order sentence φ of quantifier-rank k is preserved under homomorphisms on finite structures, then it is equivalent on finite structures to an existential-positive sentence of quantifier-rank kO(1). Quantitatively, this improves the result of , where the upper bound on the quantifier-rank of is a non-elementary function of k.
Volume / Issue
International Standard Serial Number (ISSN)
International Standard Book Number 13 (ISBN-13)
Digital Object Identifier (DOI)