2026-07-22T21:01:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8143 2024-03-06T10:39:19Z ddc:004 open_access

An Improved Homomorphism Preservation Theorem From Lower Bounds in Circuit Complexity Rossman, Benjamin circuit complexity finite model theory Previous work of the author [Rossmann'08] 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 poly(k). Quantitatively, this improves the result of [Rossmann'08], where the upper bound on quantifier-rank is a non-elementary function of k. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benjamin Rossman 2017 Is Part Of LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2017.27 urn:nbn:de:0030-drops-81435 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.27 eng https://creativecommons.org/licenses/by/3.0/legalcode