An improved homomorphism preservation theorem from lower bounds in circuit complexity
Publication
, Conference
Rossman, B
Published in: Leibniz International Proceedings in Informatics, LIPIcs
November 1, 2017
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.
Duke Scholars
Published In
Leibniz International Proceedings in Informatics, LIPIcs
DOI
ISSN
1868-8969
Publication Date
November 1, 2017
Volume
67
Related Subject Headings
- 46 Information and computing sciences
Citation
APA
Chicago
ICMJE
MLA
NLM
Rossman, B. (2017). An improved homomorphism preservation theorem from lower bounds in circuit complexity. In Leibniz International Proceedings in Informatics, LIPIcs (Vol. 67). https://doi.org/10.4230/LIPIcs.ITCS.2017.27
Rossman, B. “An improved homomorphism preservation theorem from lower bounds in circuit complexity.” In Leibniz International Proceedings in Informatics, LIPIcs, Vol. 67, 2017. https://doi.org/10.4230/LIPIcs.ITCS.2017.27.
Rossman B. An improved homomorphism preservation theorem from lower bounds in circuit complexity. In: Leibniz International Proceedings in Informatics, LIPIcs. 2017.
Rossman, B. “An improved homomorphism preservation theorem from lower bounds in circuit complexity.” Leibniz International Proceedings in Informatics, LIPIcs, vol. 67, 2017. Scopus, doi:10.4230/LIPIcs.ITCS.2017.27.
Rossman B. An improved homomorphism preservation theorem from lower bounds in circuit complexity. Leibniz International Proceedings in Informatics, LIPIcs. 2017.
Published In
Leibniz International Proceedings in Informatics, LIPIcs
DOI
ISSN
1868-8969
Publication Date
November 1, 2017
Volume
67
Related Subject Headings
- 46 Information and computing sciences