An improved homomorphism preservation theorem from lower bounds in circuit complexity

Conference Paper

Previous work of the author [39] 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 [39], where the upper bound on the quantifier-rank of is a non-elementary function of k.

Full Text

Duke Authors

Cited Authors

  • Rossman, B

Published Date

  • November 1, 2017

Published In

Volume / Issue

  • 67 /

International Standard Serial Number (ISSN)

  • 1868-8969

International Standard Book Number 13 (ISBN-13)

  • 9783959770293

Digital Object Identifier (DOI)

  • 10.4230/LIPIcs.ITCS.2017.27

Citation Source

  • Scopus